[JAVA] 백준 2437번 : 저울

 

---

 

• 코드

정답 코드 : 그리디 알고리즘 문제이다. 1시간동안 여러가지 방법으로 고민해보았는데 시간안에 풀 수 있는 뚜렷한 방법이 생각나지 않았다...(ㅠㅠ)

 

그래서 코드를 찾아본 결과 

 

현재 올리려는 저울추의 무게가, 지금까지 올린 저울추의 총합보다 커지면 저울추의 총합은 측정할 수 없는 최솟값이다.

 

현재까지 오름차순으로 정렬된 배열을 순서대로 더해준 값+1보다 해당 index의 값이 크면 그 전의 더해준 값들로는 구할 수 없다는 것이 결론이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Algorithm {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());

		// 무게 순으로 정렬
		Arrays.sort(array);

		int sum = 0;
		for (int i = 0; i < N; i++) {
			if (sum + 1 < array[i]) {
				break;
			}
			
			sum += array[i];
		}

		System.out.println(sum + 1);
	}
}