#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long int ull;
const ull MAXW = 1000000000;
//possiblew[무게]: 주어진 추로 무게를 만들 수 있는지 없는지 불린값 저장
bool possiblew[MAXW + 1];
bool compare(int a, int b) {
return a > b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<int> w;
//주어진 추로 만들 수 있는 최대 무게
ull maxw = 0;
for (int i = 0; i < n; ++i) {
int input;
cin >> input;
w.push_back(input);
maxw += input;
}
//추 내림차순 정렬
sort(w.begin(), w.end(), compare);
for (auto it = w.begin(); it != w.end(); ++it) {
for (int j = maxw - *it; j > 0; --j) {
if (possiblew[j])
possiblew[j + *it] = true;
}
possiblew[*it] = true;
}
for (int i = 1; i <= maxw; ++i) {
if (possiblew[i] == false) {
cout << i;
return 0;
}
}
cout << maxw + 1;
return 0;
}
이 문제의 키 포인트는 추로 측정할 수 있는 무게의 기존 구간과 새롭게 생긴 구간이 연속되는가?를 판단하는 것이다
ex.
7
3 1 6 2 7 30 1
추의 무게 오름차순으로 정렬: 1 1 2 3 6 7 30
(1) 사용하는 추 : 1
-> 측정할 수 있는 무게의 구간:
(2) 사용하는 추 : 1 1
-> 측정할 수 있는 무게의 구간:
(3) 사용하는 추 : 1 1 2
-> 측정할 수 있는 무게의 구간:
(4) 사용하는 추 : 1 1 2 3
-> 측정할 수 있는 무게의 구간:
(5) 사용하는 추 : 1 1 2 3 6
-> 측정할 수 있는 무게의 구간:
(6) 사용하는 추 : 1 1 2 3 6 7
-> 측정할 수 있는 무게의 구간:
(7) 사용하는 추 : 1 1 2 3 6 7 30
-> 측정할 수 있는 무게의 구간:
-> 구간의 무게는 측정할 수 없다
지금까지 구간이 끊기지 않았다면, 기존 구간:
-> 무게가 weights[i]인 추가 더해진다면, 새롭게 생긴 구간:
-> 위의 두 구간이 끊어지지 않으려면 weights[i] <= psum[i-1] + 1을 만족해야 한다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef int unsigned long long ull;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ull weight[1001];
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> weight[i];
sort(weight, weight + n);
ull psum = 0;
for (int i = 0; i < n; ++i) {
if (weight[i] > psum + 1) {
cout << psum + 1;
return 0;
}
psum += weight[i];
}
cout << psum + 1;
return 0;
}