2437

알고리즘/acmicpc 2015. 10. 9. 19:47 Posted by 아는 개발자

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


이건 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;
}
728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

11000  (0) 2015.10.11
2405  (0) 2015.10.09
2437  (0) 2015.10.09
2616  (0) 2015.10.03
2463  (0) 2015.09.29
9079  (0) 2015.09.13