백준 - 저울 2437

---

문제 분석

처음에는 경우의수를 DFS로 구하려다가 알고리즘 분류 힌트를 보고 안쓰고 풀 수 있다는 방법이 있다는것을 찾아야했다.

아무리 생각해도 모르겠어서 다른 사람 풀이방식만 참고했다. 

누적된 수의 +1 보다 다음수가 크다면 안된다는 것이다

sum+1 >= array[i] 를 만족해야 한다는 것이다. 

처음에 sum은 +1까지하면 1이니까 첫번째 수가 1보다 큰 수가 오면 안될것이다 그다음 누적의 수는 2 인데 2보다 큰수가 오면 조합이 안된다.

 

 

 

 

 

전체 소스

import java.util.*;
import java.io.*;


public class Main {


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int repeat = Integer.parseInt(br.readLine());
        StringTokenizer st= new StringTokenizer(br.readLine(), " ");
        int[] array = new int[repeat];
        
        for(int i=0; i<repeat; i++) {
        	array[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(array);
        
        int sum = 0;
        
        for(int i=0; i<repeat; i++) {
        	if(sum+1>=array[i]) {
        		sum += array[i];
        	}else {
        		break;
        	}
        	
        }

        
        System.out.println(sum+1);
		

  
    }
}

 

 

 

 

 

---

문제

예제 입력 1 

7
3 1 6 2 7 30 1

예제 출력 1 

21