[백준] 2437번: 저울(그리디)

https://www.acmicpc.net/problem/2437

2437번: 저울

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] arr = new int[N];
		int sum = 1;	
		for(int i=0; i<N; i++) 
			arr[i] = scan.nextInt();
			
		Arrays.sort(arr);
		for(int i=0; i<arr.length; i++) {
			 if(sum < arr[i])
				 break;
			 sum += arr[i];
		}
		
		System.out.println(sum);
		scan.close();
	}

}

풀이

문제를 고민하다가 추들을 하나씩 재가면서 잴 수 없는 최소값을 구하는 식으로 해결하려고 했지만 도통 해결방법을 모르겠어서 풀이를 봤다.

 

문제에 주어진 입력을보면 3 1 6 2 7 30 1 과 같다.

이 수를 오름차순으로 정렬하면 1 1 2 3 6 7 30 <- 다음과 같이 된다.

 

첫 번째 원소인 1은 만들 수 있고, 

두 번째 원소인 1을 보면 1, 1+1=2 이므로 1, 2를 만들 수 있다.

세 번째 원소인 2를 보면 1, 2, 3, 4로 1~4까지의 모든 수를 만들 수 있다.

네 번째 원소인 3을 보면 세번째 원소인 2까지 만들 수 있는 1~4에서 3을 더하면 1~7까지 모든 수를 만들 수 있다.

다섯 번째 원소인 6을 보면 1~7까지의 수와 6을 더해 1~13까지 모든 수를 만들 수 있다.

여섯 번째 원소인 7을 이용하면 20을 만들 수 있다.

하지만 일곱 번째 원소를 이용해도 21은 만들 수 없다.

 

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

저울추의 총합을 초기에 1로 설정한 이유는, 저울추의 무게 중 가장 가벼운것이 1보다 크면, 1은 측정할 수 없기때문에 1로 초기값을 설정했다.

 

사실 위 파란색이 문제의 전부인데, 위의 조건을 어떻게 생각해야 할지,, 다음에 다시 풀어봐도 못풀 것 같다.