풀이
일단 주어진 추들의 무게를 정렬해 보자.
1~w까지의 모든 무게를 만들 수 있다고 가정하자.
1~w를 만들 수 있다면
여기에 무게 k의 추를 추가해서 1~w+k까지의 모든 무게를 만들 수 있다.
하지만 만약 k > w+1이라면 w+을 만들 수 없게 된다.
이제 코드로 옮겨보자.
코드
#include <cstdio>
#include <algorithm>
int n, a[1001];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
std::sort(a, a+n);
int mx = 0;
for (int i = 0; i < n; i++) {
if (a[i] > mx+1) {
break;
}
mx += a[i];
}
printf("%d\n", mx+1);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이