[그리디] BOJ 2437 저울

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

2437번: 저울

 

문제 해결 알고리즘

 

모든 추의 무게를 정렬 해준 후에 자기보다 왼쪽에 있는 추들의 무게의 합보다 크면 그 합에 +1인 값을 출력해주면 된다. 만약에 없다면 모든 추의 무게의 합에 +1을 해준 값을 출력해준다.

 

이 때, 만약 가장 무게가 가벼운 추의 무게가 1보다 크다면 1을 출력해준다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> v(N);

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

    sort(v.begin(), v.end());
    
    int sum = v[0];
    
    if(v[0] > 1){
    	cout << 1;
    	return 0;
    }

    for(int i=1;i<N;i++){
        
        if(v[i] - 1 > sum) break; 
        sum += v[i];
    }

    cout << sum+1;
}