ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2437
    알고리즘/acmicpc 2015. 10. 9. 19:47

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


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

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

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

    댓글

Designed by Tistory.