백준 / 2437 저울 C++

www.acmicpc.net/problem/2437

2437번: 저울

추가 주어졌을 때 그 추들의 합으로 표현 불가능한 가장 작은 수를 찾는 문제입니다.

우선 추를 정렬 시킨 뒤, 첫 번 째 추가 1보다 크면 무조건 1은 표현할 수 없는 가장 작은 수입니다.

 

그리고 무게가 1인 추가 있는 경우, 정렬되어 있으므로, 두 번 째 추부터 더하면서 (합 +1)보다 크면 합+1 이란 수는 표현할 수가 없습니다.

 

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

using namespace std;

int n;
vector<int>v;
void weight()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
}

int main()
{
	weight();
	int res = 1;

	if (v[0] > 1) {
		cout << res;
		return 0;
	}

	for (int i = 1; i < n; i++) {
		if (v[i] > res + 1)
			break;
		res += v[i];
	}
	cout << res + 1;
}