백준 2437(저울) c++

문제

2437번: 저울

저울추가 주어지면 저울추로 잴 수 없는 가장 작은 수를 출력하면 됩니다.

단순히 문제만 보면 쉬워 보이지만 마땅히 생각이안나서 구글의 힘을 빌렸던 문제 입니다.

코드를 살펴보겠습니다.

---

int n;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++) {
	cin >> v[i];
}
sort(v.begin(), v.end());

먼저 저울이 개수인 n을 입력바고 n만큼 저울의 무게를 입력받아 벡터 v에 저장합니다.

그다음 오름차순으로 정렬을 해줍니다. 가장 작은 수 부터 하나하나 체크해 만들 수 없는 저울의 무게를 알아보기 위함입니다. 문제에서도 저울로 잴 수 없는 가장 작은 수를 출력하라고 했기 때문 입니다.

ll sum = 0;
for (int i = 0; i < n; i++) {
	if (sum + 1 < v[i]) {
		break;
	}
	else sum += v[i];
}
cout << sum + 1;

변수 sum은 지금까지 무게추들의 누적합 입니다. 다시 말해 sum 이하의 무게들은 다 무게를 잴 수 있다는 것입니다.

그러므로 sum+1의 값보다 다음 무게추가 크면 sum+1의 값은 무게를 재지 못하므로 저울로 무게를 잴 수 없는 

가장 작은 값이 됩니다.

예를들어 무게 추가 1, 1, 2, 10 이있다고 할때, sum=0부터 시작하면 

sum(0)+1=1 이 첫번째 추의 무게 1보다 크거나 같으므로 무게 1은 잴 수 있습니다. sum에 누적합으로 더해줍니다.

sum(1)+1=2 이 두번째 추의 무게 1보다 크거나 같으므로 무게 1은 잴 수 있습니다. sum에 누적합으로 더해줍니다.

sum(2)+1=3 이 세번째 추의 무게 2보다 크거나 같으므로 무게 2는 잴 수 있습니다. sum에 누적합으로 더해줍니다.

지금까지 sum의 누적합은 4이므로 1부터 4까지 무게를 잴 수 있다는 의미입니다. 

1, 2, (1+2), (1+1+2)

sum(4)+1=5 가 네번째 추의 무게 10보다 작으므로 무게 4부터 10사이에 수(5,6,7,8,9)를 잴수 없게 됩니다.

따라서 그중 가장 작은수를 출력해야하므로 sum+1=5가 잴 수 없는 수중 가장작은수가 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		if (sum + 1 < v[i]) {
			break;
		}
		else sum += v[i];
	}
	cout << sum + 1;
	
	return 0;
}