[알고리즘] 만들 수 없는 금액 (그리디)

문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.

입력조건

• 첫째 줄에는 동전의 개수를 나타내는 양의정수 N이 주어집니다(1<=N<=1000)
• 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때 각 화폐 단위는 1,000,000이하의 자연수입니다.

출력조건

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 만들수없는금액 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        Integer coin[] = new Integer[N];
        int target=1;
        for (int i=0;i<N;i++) {
            coin[i] = Integer.parseInt(s[i]);
        }

        Arrays.sort(coin);

        for (int i=0;i<N;i++) {
            if(target< coin[i]) break;
            target+=coin[i];
        }

        System.out.println(target);
    }
}

풀이

• target : 만들 수 있는 금액인지 확인하는 변수

그리디 알고리즘을 이용하여 정렬된 배열의 앞에서부터 차례로 탐색을 한다. 이 때 현재까지의 합까지는 만들 수 있는 금액이다.

예를 들어 설명하면 3 2 1 1 9 라는 입력이 있다고 하자
정렬을 통해 1 1 2 3 9가 된다.

1) target = 1 + 1 = 2
1은 만들 수 있으니 다음 타겟인 2로 넘어감
2) target = 2 + 1 = 3
위에서 1을 만들 수 있고, 여기서 1을 더하면 2이므로 1~2까지는 만들 수 있음. 따라서 다음 타겟인 3으로 넘어감
3) target = 3 + 2 = 5
위에서 1~2까지 만들수 있고, 1~2에 각각 2를 더하면 3~4도 만들 수 있으므로 1~4까지 만들 수 있다. 따라서 다음 타겟인 5로 넘어감
3) target = 5 + 3 = 8
1~4까지 만들 수 있고 1~4에 각각 3을 더하면 4~7도 만들 수 있으므로 1~7까지 만들 수 있을 것이다. 따라서 다음 타겟인 8로 넘어감
4) target <coin[i] (=9)이므로 break;
1~7까지 만들수 있고 1~7에 각각 9를 더하면 10~16까지 만들 수 있다. 그러나 8과 9는 만들 수 없게 된다. 따라서 현재 타겟인 8이 만들 수 없는 금액의 최솟값이 된다.

느낀점

솔직히 풀이를 봐도 뭔소리인지 몰라서 한참을 들여다 보았다. 이제 이해는 됐는데 나중에 이걸 생각해내기에는 쉽지 않을 것 같다...