2437

이것도 스스로 못풀고 인터넷에 있는 풀이를 보고 풀었는데 정말 어떻게 이걸 생각해냈는지 대단하다는 느낌이 들면서도 간단한 풀이를 생각하지 못한 스스로에게 반성하게 되었다.

이건 dp문제로도 볼 수 있다.

먼저 추들을 정렬한다. 그리고 k는 1~N 사이에 있는 수로 가정하자

나는 1~k번까지의 추들을 통해서 최대 M까지의 무게를 만들 수 있다 치자(만약 못 만든다면 그전에 끝내버리면 된다)

이제 나는 k+1번째 추를 추가하고 싶다.

그런데 k+1번째 추의 무게가 M+1이 아니고 1을 더해서(1을 더하는 이유는 앞에서 내가 1부터 만들어 낼 수 있기 때문이다) M+1보다 크다면 나는 죽었다 깨어나도 주어진 추들의 조합으로 M+1을 만들 수 없다. 왜냐면 k+1보다 뒤에 있는 추들은 k+1보다 무거운 추들이기 때문에 얘네들로는 절대 못만든다.

만약 위와 같은 경우에수가 생긴다면 나는 M+1의 추를 만들 수 없는 것이다.

이런문제를 초딩이 풀다니...

 
#include<cstdio>
#include<algorithm>

using namespace std;

int d[1005];
int main(){
	int N;
	scanf("%d", &N);

	for(int i=0; i<N; i++)
		scanf("%d", &d[i]);

	sort(d, d+N);

	int makable=1;
	if(d[0]!=1){
		printf("1\n");
		return 0;
	}
	else{
		for(int i=1; i<N; i++){
			if(d[i]!=makable+1 && d[i]+1 > makable+1){
				printf("%d\n", makable+1);
				return 0;
			}
			makable += d[i];
		}
	}
	printf("%d\n", ++makable);

	return 0;
}