저울 (백준 - 2437번)

 

우선 입력받은 추의 무게를 오름차순으로 정렬해야 한다.

 

정렬된 상태에서 맨 처음 추의 무게가 1이 아닌 경우에 측정할 수 없는 최소 무게는 1이다.

 

만약 맨 처음 추의 무게가 1인 경우 1을 시작으로 두번째 추부터 마지막 추까지 무게를 차례대로 더해주도록 한다. 무게가 적은 추부터 차례대로 더하는 sum이라는 값이 있다고 하자. 차례대로 sum에 추의 무게를 더해주는 도중에 sum + 1이면서 sum + 1값이 입력받은 어떤 추에도 존재하지 않는 값이라면 그것은 측정할 수 없는 최소 무게가 될것이다.

 

코드는 다음과 같다.

 

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

int main()
{
	int N;
	cin >> N;
	vector<int> sinkers;

	for (int i = 0; i < N; ++i)
	{
		int input;
		cin >> input;
		sinkers.push_back(input);
	}

	sort(sinkers.begin(), sinkers.end());
	
	if (sinkers[0] != 1)
		cout << 1 << endl;
	else
	{
		int sum = 1;
		for (int i = 1; i < N; ++i)
		{
			if (sinkers[i] > sum + 1)
				break;
			sum += sinkers[i];
		}

		cout << sum + 1 << endl;
	}
}