[C++] 백준 2437 - 저울

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

2437번: 저울

<풀이>

1. 저울추를 입력받는다.

2. 저울추를 정렬한다.

3. 결과값을 구하고 출력한다.

​

<해법>

1. 측정할 수 없는 무게를 구하는 방법.

=> 만약 내가 가지고 있는 저울추들로 1~K무게를 모두 만들 수 있다고 가정합니다. 다음 저울추(L)가 K무게 보다 같거나 작다면, 다음 저울추로 (1+L)~(K+L)무게를 모두 만들 수 있습니다. 그렇다면 다음 저울추까지 포함하면 1~(K+L)무게를 모두 만들 수 있는 것이 됩니다.

 

간단하게 예를 들면 가지고 있는 저울추들로 1,2,3,4 무게를 만들 수 있다고 해보겠습니다.

다음 저울추가 5라면 5,6,7,8,9 무게를 만들 수 있을 것이다. 따라서, 1~9 무게를 모두 만들 수 있습니다.

하지만, 다음 저울추가 6라면 6,7,8,9,10 무게를 만들 수 있게되어 무게 5는 측정을 하지 못합니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[1000];
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    //정렬
    sort(arr, arr + N);
    
    //결과값 구하기
    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }
 
    //출력
    cout << res;
}

 

수학적인 사고에 대해 알아볼 수 있는 문제였습니다.