[C++] 백준 온라인 저지 2437번 저울 풀이

주어지는 저울들로 잴 수 없는 무게 중 가장 적은 값을 구하는 문제

 

---

 

문제의 조건

 

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

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

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

 

입력

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

 

출력

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

 

 

풀이 과정

 

 만들 수 있는 합을 하나하나 만들어 봐야 하나? 이런저런 생각을 했지만 영 아이디어가 떠오르지 않아서 구글링을 해 보았습니다. 

 

https://aerocode.net/392

백준 2437 풀이 및 해설

 

 그 중 가장 설명이 잘 되어 있는 블로그. 친절하게 그림과 함께 한 단계씩 설명이 되어 있어서 이 문제를 푸는 방법을 확실하게 이해할 수 있습니다. 

 

1. 입력받은 수들을 오름차순으로 정렬한다. 

 

2. 정렬한 수들의 누적합계를 구하면서 i번째 원소가 누적합계 + 1 보다 크다면 누적합계를 구하는 것을 중단하고 그 전까지 구한 누적합계+1 값을 출력한다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    unsigned N;
    cin >> N;
    
    vector<unsigned> weights(N, 0);
    for (int i = 0; N > i; i++)
        cin >> weights[i];
    
    sort(weights.begin(), weights.end());
    
    unsigned sum = 0;
    for (int i = 0; weights.size() > i; i++)
    {
        if (sum + 1 < weights[i])
            break;
        
        sum += weights[i];
    }
    
    cout << sum + 1;
    
    return 0;
}