[BOJ 2437 // C++] 저울

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2437번 문제인 저울이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2437

2437번: 저울

 

이 문제를 knapsack 문제를 해결하듯이 dp를 이용해서 풀려고 시도할 수는 있겠지만, 이 문제에 하기에는 나올 수 있는 숫자의 범위가 넓어 사용하기 좋은 방법이 아니다.

 

이 문제에서 요구하는 것은 주어진 추들로 구성하지 못하는 최소 정수이므로, 다음과 같은 과정으로 작은 무게의 추부터 순서대로 살펴보는 것으로 만들 수 없는 가장 작은 무게의 조합을 빠르게 계산해낼 수 있다.

 

1) 주어진 추 가운데 무게가 1인 추가 없다면 1이 만들 수 없는 가장 작은 무게임은 자명하다.

2) 가장 가벼운 추부터 i번째로 가벼운 추까지 사용하여 만들 수 있는 추의 무게의 범위가 1 이상 K 이하라고 가정하자(i > 0).

2-1) i+1번째로 가벼운 추의 무게 X가 K+1 이하라면, 가장 가벼운 추부터 i+1번째로 가벼운 추까지 사용하여 만들 수 있는 추의 무게의 범위는 1 이상 K+X 이하이다. K의 값을 K+X로 갱신하고, 2)로 돌아가 다음 추를 살펴보자. 다음 추가 없다면 답으로 K+1을 출력하고 프로그램을 종료한다.

2-2) i+1번째로 가벼운 추의 무게 X가 K+1을 넘어간다면, 주어진 추로 K+1이라는 무게를 측정할 수 없음을 알 수 있다. 남은 추의 무게는 모두 K+1을 넘어가기 때문이다. 따라서 답으로 K+1을 출력하고 프로그램을 종료한다.

 

아래는 제출한 소스코드다. 위의 내용을 그대로 구현한 것으로, 특별한 주석은 달지 않았다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1000];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        cin >> arr[i];
    }
    
    sort(arr, arr + N);

    if (arr[0] != 1) {
        cout << 1;
        return 0;
    }

    int ans = 1;
    for (int i = 1;i < N;i++) {
        if (arr[i] <= ans + 1) ans += arr[i];
        else break;
    }

    cout << ans + 1;
}