[백준] 2437 저울 [자바]

 

---

 

 

https://plplim.tistory.com/59

[백준 #2437번 JAVA] 저울 풀이

 

※. [3 1 6 2 7 30 1] 의 합은 50이다. 이 때 50 + 1 = 51은 절대 측정할 수 없는 양의 무게다.

 

※. 1,2,3,4 일 때 절대 측정할 수 없는 수는 11이다.(합이 10일때 1~10까지 모든 수를 측정할 수 있다.)

 

※. 1,3,4 일 때 측정할 수 없는 수는 2이다.(1 + 1)

 

※ 배열을 오름차순으로 정렬한 뒤 누적합을 구한다.

(누적합 + 1 은 측정할 수 없는 수다. 그러나 누적합+1이 다음값 b보다 크다면 {b+1,b+2....b+누적합} 까지 가능하다.)

(1,2,3 의누적합+1 = 7 이지만 다음값b = 6 일 때 -> 1+6, 2+6...1+2+3+6 까지 가능)

(누적합 + 1 이 다음값 b보다 작다면 누적합 + 1은 절대 측정할 수 없는 수다. -> 오름차순 순서로 누적합을 구했기 때문에 1을 포함한 b보다 작은수의 추는 없다.)

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		long sum = 1; //추의 합보다 1이 크다
		for(int i : arr) {
			if(sum < i) break;
			sum += i;
		}
		
		System.out.println(sum);
	}
}