백준 2437: 저울 - javascript(그리디)

문제 출처 

https://www.acmicpc.net/problem/2437

 

정답 풀이 

이건 문제 푸는 아이디어를 생각하기 정말 어려웠을 것 같다. 

나도 여러 블로그를 통해 이해가 됐고, 

만약 이런 방식으로 설명이 되어 있었다면 ,

이해가 좀 더 수월할 수 있었을 것 같은 방식으로 이야기 해보려고 한다. 

 

[1,1,2,3,6,7,30] 배열이 주어졌다고 가정하자. 

이해하기 쉽게 중간부터 흐름을 따라가보자. 

 

1,1,2,3 으로 표현할 수 있는 

최솟값은 1이다. 

최댓값은 7이다.  (1 + 1 + 2 + 3)

 

 

 

그 다음 숫자 6을 넣으려고 할 때, 6이 내포하는 의미가 무엇이겠는가? 

적어도 6을 표현할 수 있고, 

이전 숫자들로 표현할 수 있었던 값 7과 더한다면 최대로 13을 표현할 수 있다는 뜻이 된다. 

 

그리고 우린 가정한다. 일단 전 숫자들로 7까지는 다 표현할 수 있었겠구나라고 !! 

1,2,3,4,5,6,7 이 표현 가능했다는 뜻은 ? 

6을 더했을 때 

7,8,9,10,11,12,13이 표현 가능하다는 뜻이다. ~~ 

 

 

애매하게 이해가 가더라도 일단 진행해보자 

 

그 다음 숫자 7을 넣을 때는 ? 

의미하는 것이 무엇인가 

적어도 7을 표현할 수 있고, 

이전 에 표현할 수 있었던 최댓값인 13 과 7을 더해서 최대로 20까지도 표현할 수 있다는 뜻이 된다. 

다음 숫자인 30을 넣을 때는??

적어도 30은 표현할 수 있고, 

이전의 숫자들로 표현할 수 있었던 최대값 20과 더했을 때 50까지 표현할 수 있다는 것이다. 

 

 

그런데 잠시만 stop ~~~ 

 

보라색 부분을 봐보자 

검정에서 => 주황 으로 넘어갈 땐 숫자가 비는 곳이 없다. 

주황에서 => 초록 으로 넘어갈 땐 숫자가 비는 곳이 없다. 

초록에서 => 빨강 으로 넘어갈 땐 숫자가 21부터 29까지 빈다. 

 

즉, 해당 배열로 표현할 수 없는 최솟값은 21이 된다. 

 

이것의 규칙을 정리하자면, 

우리가 현재 구할 수 있는 최대값 20을 이어서 1만큼 큰 숫자보다 작은 숫자가 들어왔어야 계속 연속적으로 숫자를 표현할 수 있었던 것이다. 

즉, 우리가 현재까지 구할 수 있는 숫자(20) +1 보다 새로 들어올 숫자 (30)가 컸기 때문에 숫자 사이의 빈공간이 생겨버렸다.

코드로는, `sum + 1 >= new_number` 이렇게 표현할 수 있겠다. 

 

그럼 코드는 작성할 수 있다. 

 

추가로 하나의 설명을 붙이자면, 

우리가 문제를 풀면서 당연하게 가정한 것이 있었는데 

지금까지의 합 이전의 모든 수를 표현 가능하다고 가정했었다. 

지금까지 설명을 다 이해했다면, 당연히 이제는 납득이 가야한다. 

 

왜냐? 우리는 반복문을 통해 계속 새로운 값을 넣어준건데 

20과 30 사이의 값처럼 중간에 비어있는 부분이 있다면 애초에 반복문이 끝나고  정답을 return 했을 것이다. 

 

그러나, 현재 숫자들의 합을 넘겨받았다는 건, 

즉, 뭐다? 

1부터 현재 숫자까지는 다 표현할 수 있으니, 안심하란 뜻으로 받아들일 수 있다 ~ 

정답 코드 

let [n, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
n = Number(n)
let arr = input[0].split(' ').map(v => +v).sort((a,b) => a-b)
function solution(n, arr){
    let sum = 0; 
    for(let new_number of arr){
        if(sum + 1 >= new_number){
            sum += new_number
        }else{
            break; 
        }
    }
    return sum + 1
}

console.log(solution(n, arr))