[백준 2437 - C++] 저울 : 그리디 알고리즘

www.acmicpc.net/problem/2437

2437번: 저울

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

7

3 1 6 2 7 30 1

예제 출력 1 

21

 

풀이

이런 문제 풀이 방법을 뚝딱 생각해내는 사람은 대체 뭘까? 천재인걸까...?

일단은 받아온 추의 무게를 오름차순으로 정렬해 주어야 한다.

그뒤로는 막혀서 결국 질의응답에 사람들이 푼 내용을 보고 깨달았다..

sum=1 부터 시작해서 정렬된 추의 무게와 차례대로 비교하고 sum이 더 큰 경우엔 sum에 그 추의 무게를 더하고 계속 반복한다.

만약 sum이 더 작은 경우엔 sum의 무게가 측정할 수 없는 양의 정수 무게중 최솟값이 된다.

대체 어떻게 이런 방법을 생각하는 걸까... 놀랍다ㅠ

 

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int weight[1000];

priority_queue<int> pq;

int main(void){
    int n, w;
    int sum = 1;
    
    scanf("%d", &n);
    
    for(int i=0; i<n; i++){
        scanf("%d", &w);
        pq.push(-w);
    }
    for(int i=0; i<n; i++){
        weight[i] = -pq.top();
        pq.pop();
    }
    for(int i=0; i<n; i++){
        if(sum < weight[i])
            break;
        sum += weight[i];
    }
    printf("%d\n", sum);
}