백준 - 2437번 : 저울 (C++)

풀이 방법 : 그리디

주어진 숫자들의 합으로 만들 수 없는 최소인 양의 정수를 출력하는 문제다.

먼저 입력으로 주어진 추들을 오름차순으로 정렬 하고 가벼운 추부터 시작해서 비교해가기 시작한다.

현재 무게는 1부터 시작해간다. 만약 현재 무게보다 비교하는 추가 더 무거울 경우 그 이후에 등장하는 추는 현재 추보다 더 무거운 추밖에 없을 것이기 때문에 해당 무게는 가지고 있는 추로는 측정할 수 없다는 것이 된다.

예를 들어 처음 등장하는 추가 2라면 1보다 2가 크다 오름차순으로 정렬했기 때문에 남은 추중에 2보다 작은 것은 없으므로 가지고 있는 추로는 1의 무게를 측정할 수 없다.

무게가 작거나 같다면, CurWeight에 해당 추의 무게를 더해주면서 같은 과정을 반복해가면 된다.

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

using namespace std;


int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> vecWeight(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> vecWeight[i];
	}

	sort(vecWeight.begin(), vecWeight.end());
	int CurWeight = 1;

	for (int i = 0; i < N; ++i)
	{
		if (CurWeight < vecWeight[i])
		{
			break;
		}

		CurWeight += vecWeight[i];
	}

	cout << CurWeight;

}

예전에 이거랑 비슷한데 N이 적게 주어지는 문제 백트래킹으로 푼 다음에 다른 고수들의 풀이 찾아보다가 발견한 풀이인데 기억해두길 잘했다. 역시 한 문제를 풀면 다른 풀이도 찾아봐야 공부가 된다.