문제

나의 요약

양팔 저울로 물건 무게 측정한다.
저울의 한쪽에는 저울추, 다른쪽에는 측정하려는 물건만 올려놓을 수 있다.
N개의 저울추가 주어질 때, 추들을 사용해 측정할 수 없는 양의 정수 무게 중 최솟값을 출력하자.

접근 방법

N이 최대 1000이기 때문에, 조합을 이용한 백트래킹 기법으로는 불가능하다. 한 추가 늘어날 때마다 경우의 수가 2의 지수로 늘어나기 때문에 때문에, DP로도 불가능하다.

따라서 추를 한번에 순회하면서 알아낼 수 있는 방법이 필요하다.
예시에 나온 3, 1, 6, 2, 7, 30, 1의 저울추를 보자. 이를 정렬하면, 1, 1, 2, 3, 6, 7, 30이다.

이제 이를 순서대로 더해보자.
1. 먼저 1이 더해진다.
2. 1+1으로 합은 2가 된다. 1, 2를 모두 측정할 수 있기 때문에 문제 없다.
3. 2+2으로 합은 4가 된다. 4를 측정할 수 있고, 앞에서 이미 1을 측정할 수 있었기 때문에 4-1=3도 측정이 가능하다.
4. 4+3으로 합은 7이 된다. 7을 측정할 수 있고, 앞에서 이미 1, 2를 측정할 수 있었기 때문에 7-1=6, 7-2=5도 측정이 가능하다.
5. 7+6으로 합은 13가 된다. 13을 측정할 수 있고, 앞에서 이미 1, 2, 3, 4, 5를 측정할 수 있었기 때문에 13-1=12, 13-2=11, 13-3=10, 13-4=9, 13-5=8도 측정이 가능하다.
6. 13+7으로 합은 20가 된다. 20을 측정할 수 있고, 앞에서 이미 1, 2, 3, 4, 5를 측정할 수 있었기 때문에 20-1=19, 20-2=18, 20-3=17, 20-4=16, 20-5=15, 20-6=14도 측정이 가능하다.
7. 20+30으로 합은 50가 된다. 50을 측정할 수 있지만, 전의 합이 20이었으므로 30까지만 모든 수의 측정이 가능하다. 즉, 21~29까지는 측정이 불가능한 것이다.

여기서 알 수 있는 것은, 정렬이 되어있는 상태에서 0~i까지의 합이 i+1 추의 무게보다 작다면, 그 합 이후로의 숫자는 측정이 불가능한 것이다. 이대로 코드를 작성하면 된다.

풀이

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

int N;
vector<int> weight;

void Input()
{
    cin >> N;
    weight.resize(N);
    for(int i = 0; i < N; i++)
    {
        cin >> weight[i];
    }
}


void Solve()
{
    sort(weight.begin(), weight.end());

    if(weight[0] != 1)
    {
        cout << 1;
        return;
    }
    
    long long sum = weight[0];
    
    for(int i = 1; i < N; i++)
    {
        if(sum < weight[i] && sum + 1 != weight[i])
        {
            break;
        }
        sum += weight[i];
    }
    cout << sum + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

접근 방법과 동일하게 구현했다. 여기서 중요한 점은, 0~i번째까지의 합이 i+1번째의 추 무게보다 작더라도, 추 무게가 1만 큰 상황이라면 측정 가능한 무게가 연속적으로 증가한다는 것이다. 예를 들어 합이 20이었을 때, 다음 추가 21이라면, 추가 21을 자동으로 채워주기 때문에 연속 측정에 문제가 없다.

회고

위의 접근 방법에만 50분을 썼다.. 처음에 백트래킹, DP, 등등을 생각했지만 도저히 되지 않아, 색다른 풀이가 분명 존재할 것이라 생각했다. 그 부분에 집중해서 언제 연속 측정이 되지 않는지를 생각했다. 접근에 성공했더니 코드 자체는 금방 구현해서, 접근을 1시간 이내로 해냈다는 것에 만족했다.