[백준]2437번. 저울

[문제]

 

www.acmicpc.net/problem/2437

2437번: 저울

 

[풀이]

 

추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다.

 

아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다.

풀이는 그리디 알고리즘으로 구현했다. 

 

주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때,

더하려는 추의 무게가 sum+2보다 크거나 같다면

sum+1의 무게는 측정할 수 없다.

 

풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 이런 방식을 생각해내는지 모르겠다. 

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int arr[MAX]={0,};
int N;

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    sort(arr,arr+N);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        if(sum+2<=arr[i]){
            cout << sum+1;
            return 0;
        }
        sum+=arr[i];
    }
    cout << sum+1;
    return 0;
}