[C++]백준2437번 저울

오늘은 백준2437번 저울 문제를 풀어보도록 하자.

1부터 하나씩 하면 되겠지 라는 생각으로 했지만 시간초과가 나서 당황했다. 하지만 1억이 넘어가면 1억번 연산이기에 시간초과는 당연한 수순이였다.

그래서 고민을 하던 중 잴 수 없는 최솟값 이라는 부분에서 힌트를 얻었다.

처음 impossible_gram = 1로 놓는 이유는 잴 수 없는 최솟값 이 양의 정수 이기 때문에 impossible_gram = 0.0000001 뭐 이런 식으로

놓지 않고 impossible_gram = 1로 놓고 시작할 수 있다.

자세한건 접근법에서 알아봅시다 :)

문제는 다음과 같다.

                               [접근법]

  1. 잴 수 없는 양의 정수 중 최솟값을 도출하는 것이기에 impossible_gram = 1로 놓고 시작한다.
  
  2. 오름차순으로 정렬 후 impossible_gram보다 v[i]가 작으면 더해주고, 크면 break 후 출력해준다.

  3. 크면 break하는 이유 : 계속 더해준 impossible_gram 값 - 1까지 표현이 가능했다는 뜻. 즉, v[i]가 더 크면 impossible_gram은 표현 불가능한 값임.

                                     [코드]
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	vector<int>v;
	int num, gram, impossible_gram = 1;

	cin >> num;

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

	for (int i = 0; i < num; i++) {
		if (v[i] > impossible_gram) {
			break;
		}
		impossible_gram += v[i];
	}

	cout << impossible_gram << '\n';
	return 0;
}