[백준] 2437 저울 (C++)

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

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

 

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

---

풀이

처음 문제를 봤을 때는 DP로 접근해야 하나 생각했지만, 저울추의 무게가 중복될 수 있기 때문에 이는 어려웠다.

대신, DP로 풀 때 처럼 무게가 1일때부터 조금씩 올려가며 생각해보기로 하였다.

 

먼저 저울추를 모두 정렬하였다. 문제에 있는 예제 입력 1을 정렬하면 다음과 같다.

그리고 무게가 작은 순대로 무게추를 사용해보자.

먼저 무게가 1인 무게추를 사용하면 무게 1을 측정할 수 있다.

 

이어서 무게가 1인 무게추를 사용한다. 기존에 측정할 수 있는 무게는 1이고 이제 2의 무게를 측정할 수 있다.

이어서 무게가 2인 무게추를 사용한다. 기존에 측정할 수 있는 무게는 1~2이고 각각 2의 무게추를 더하면 3과 4의 무게를 측정할 수 있다. 따라서, 1~4의 무게를 측정할 수 있다.

 

 

이어서 무게가 3인 무게추를 사용한다. 기존에 측정할 수 있는 무게는 1~4이고 각각 3의 무게추를 더하면 4~7까지의 무게를 측정할 수 있다.

마찬가지로 무게가 6, 7인 무게추를 사용하면 각각 13, 20까지 무게를 측정할 수 있다.

 

하지만, 무게가 30인 무게추를 사용하면 30~50까지의 무게를 측정할 수 있고 무게 21은 측정할 수 없다.

위 규칙을 따라 코드를 구현하면 문제를 쉽게 풀어낼 수 있다.

 

코드

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

int weights[1000];

int main(){
    int n;
    cin >> n;

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

    int answer = 0;

    for (int i = 0; i < n; i++){
        if (weights[i] <= answer+1){
            answer += weights[i];
        }
        else{
            break;
        }
    }
    cout << answer+1;
}