(C++) - 백준(BOJ) 2437번 : 저울

BOJ 2437번 : 저울

💡 IDEA

주어진 추를 이용하여 만들 수 없는 무게의 최솟값을 ans라고 했을 때, 1 ~ ans-1 까지는 주어진 추로 측정 가능한 무게이다.

단, 위의 아이디어가 성립하기 위해서는 무게가 1인 추가 무조건 입력으로 들어와야 한다. 그렇지 않다면 무게 1을 측정할 수 있는 수단이 없기 때문이다.

위의 아이디어에 착안하여 풀이방법을 생각해보자.

---

🔑 Solution

입력으로 주어진 추의 무게들을 오름차순으로 정렬한 뒤, 두 번째 element부터 차례대로 누적합 M을 계산한다. (첫 번째 element는 위에서 말한대로 1이어야 한다.)

그렇다면 현재 상태는 1 ~ M까지는 측정할 수 있는 무게가 된다. 이 때, 누적합을 구한 element의 다음 element를 k라고 하면 측정 가능한 무게는 1 ~ M, 그리고 k, k+1, ... k+M 이 된다.

그런데 만약 k > M+1 이라고 한다면, 우리는 어떤 수를 쓰더라도 M+1을 측정할 수 없는 상태가 되어버리고 이 경우에서 M+1이 우리가 찾는 정답이 된다.

---

💻 Code

#include <bits/stdc++.h>
using namespace std;

int a[1005]; // 추들을 저장할 배열

int main(void)
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, sum = 1; // 추의 개수 N, 누적합 sum
    cin >> N;
    for(int i=0; i<N; i++) cin >> a[i];
    sort(a, a+N); // 추들을 오름차순으로 정렬
    if(a[0] != 1) { // 첫 원소는 1이어야 함
        cout << 1;
        return 0;
    }
    for(int i=1; i<N; i++) { // 만약 k > M+1이라면 탐색 종료
        if(a[i] > sum+1) break;
        sum += a[i];
    }
    cout << sum+1; // print M+1
}