[백준/BOJ] 백준 2437번 : 저울

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

2437번: 저울

추의 무게를 정렬한 뒤, check를 통해 0~check까지 만들 수 있다는 상황(초기값:0)을 저장하고, 순서대로 추를 확인하여 해당 추를 0 이상 check이하 모든 값에 각각 더한다면 0~check+해당추까지 값이 만들어질 수 있는 경우인지 확인하였다. 확인하는 방법은 0(만들 수 있는 수중 가장 작은 값이 0이므로) + 해당추의 무게가 check + 1보다 크면 check+1은 값은 만들 수 없는 최솟값임을 이용해 문제를 해결했다.

 

코드

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

int n;
vector<int> weight;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		weight.push_back(input);
	}

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

	int check = 0;
	for (int i = 0; i < n; i++)
	{
		//현재는 0~check까지 값을 만들 수 있는 상황
		//weight[i]를 0이상 check이하 모든 값에 각각 더한다면 0~check+weight[i]까지 값이 만들어질 수 있는경우인지 확인

		//0(만들수 있는수 중 가장 작은 값) + weight[i]가 check + 1보다 크면 check + 1값은 만들수 없는 최솟값이다
		if (weight[i] > check + 1)
			break;
		else
			check += weight[i];
	}

	cout << check + 1;

	return 0;
}