백준 2437 저울

사실 이문제는 다른 사람들의 풀이를 봤다. 답을 보고 어떻게 이런생각을 하지...... 라며 감탄을한 기억이 난다. 

 

여러 개의 추의 합 중 만들 수 없는 가장 작은 합을 구하는 문제이다. 

 

추들을 정렬 후

더하면서 처음으로 합보다 큰 수가 나오면 다음 값을 만들 수 없게된다. 그간 합 + 1이 답이된다. 

 

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

int N;
vector<int> input();

int main(){
	vector<int> scale = input();
	int base = 1;
	for(auto sc : scale){
		if(base < sc)
			break;
		else
			base+=sc;
		
	}

	printf("%d", base);
}


vector<int> input(){
	scanf("%d", &N);
	vector<int> scale(N, 0);

	for(int i = 0; i < N; i++)
		scanf("%d", &scale[i]);

	sort(scale.begin(), scale.end());

	return scale;
}