📝 문제 정보
🧐 관찰 및 접근
- $1, 2, 4, 8, 16, \cdots$의 추로 모든 양의 정수를 측정할 수 있음이 자명하다.
- 이 이유를 살펴보면, $X$라는 무게의 추가 있을때, $X-1$까지의 모든 정수를 표현할 수 없다면 표현할 수 있는 최대치 + 1이 답이 된다.
- 추를 작은것부터 정렬해서, 빠지는 수 없이 무슨 양의 정수까지 최대한 잴 수 있는지 확인하자.
💻 풀이
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<ll> v(N);
rep(i, 0, N) cin >> v[i];
sort(all(v));
ll sum = 0;
rep(i, 0, N){
if(v[i] > sum + 1){
cout << sum + 1 << "\n";
return;
}
sum += v[i];
}
cout << sum + 1 << "\n";
}