[알고리즘] 저울

구현 방식

• 생각하기 어려운데,, 정렬된 무게들로 확인해보자.
• 만약에 입력 예제로 무게가 2 이 들어왔다고 가정하면, 정답은 1 이 될것이다.
• 만약에 1 3 이 들어왔으면, 정답은 2 가 될것이다.
• 만약에 1 1 3 7 이 들어왔다면, 정답은 6 이 될것이다. 6 도 만들수 있으려면 7 이아니라 6 이하의 숫자가 들어왔어야한다.
• 1 까지 무게를 만들수 있다면, 2 보다 작은게 그다음 와야하고, 5 까지 만들수 있으면, 6보다 작은게 와야한다. 안그러면! N + 1 되는 무게를 만들수 없게된다.!
• 따라서, 정렬된 무게들 중 이전까지의 누적합 + 1 보다 현재 무게가 크면, [누적합 + 1] 무게가 만들지 못하는 최소무게가 된다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;


void solution(priority_queue<int, vector<int>, greater<int>>& weights);

int main()
{
	int N;
	cin >> N;
	priority_queue<int,vector<int>,greater<int>> weights;
	
	int w;
	while (N--)
	{
		cin >> w;
		weights.push(w);
	}


	solution(weights);

	return 0;
}

void solution(priority_queue<int, vector<int>, greater<int>>& weights)
{
	int w, accWeight = 0;
	while (!weights.empty())
	{
		w = weights.top();
		weights.pop();
		if (accWeight + 1 < w)
		{
			break;
		}

		accWeight += w;
	}

	cout << accWeight + 1;

}