[백준] 2437번 저울

[문제]

무게가 양의 정수인 N개의 저울 추가 주어졌을 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값 구하기.

 

[풀이]

Greedy 방식으로 해결할 수 있는 문제로, 각 추를 정렬 후 누적합을 구하면서 해결해 나갈 수 있습니다.

 

우선, 추의 배열을 w, 누적합의 배열을 acc라고 정의하겠습니다.

 

무게가 1인 추가 있을 때, acc[i-1] + 1 >= w[i] 일 경우 

acc[i-1] ~ acc[i] 사이의 모든 수를 만들 수 있습니다. 

만약 저 조건에 해당하지 않는다면 acc[i-1] + 1이 만들수 없는 수 입니다.

 

그리고 무게가 1인 추가 없다면 당연히 답은 1이겠죠?

 

문제에 제시된 예제를 통해 설명하도록 하겠습니다. 

i	0	1	2	3	4	5	6
추(w)	1	1	2	3	6	7	30
누적합(acc)	1	2	4	7	13	20	50

acc[5]을 보시면 w[6] - 1보다 작아, 해당 예시의 정답은 21 입니다.

 

처음 풀이를 알게 되었을 때는 이게 어떻게 성립하는 것인지 이해가 되지 않아서 반례를 찾아보려 했는데요..

부질없는 짓이었고 오히려 명확하게는 아니지만 어느정도 이해하게 되었습니다.. 

위 예제에서 답이 왜 21인지는 알겠지만 19, 18 뭐 이런 숫자들이 왜 다 만들 수 있는건지는 잘 이해는 안되네요 ㅎㅎ

(ps. 혹시나 원리를 설명해주실 수 있으신 분은 댓글로 설명 나눠주시면 감사하겠습니다 ^^)

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n;
    int num[1000];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    sort(num, num + n);
    int result = 1;
    if (num[0] == 1) {
        int acc = num[0];
        for (int i = 1; i < n && acc >= num[i] - 1; i++) acc += num[i];
        result = acc + 1;
    }
    cout << result;
    return 0;
}