만들 수 없는 금액

1. 문제

동전의 갯수 N개 와, 각 동전의 금액이 주어졌을 때, 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟 값을 출력 하세요. 첫째줄은 N의 값(1 <= N <= 1000) 이 주어지고, 각 동전의 단위는 1,000,000 이하의 자연수 입니다.

 

 

2. 접근

1. 주어진 동전들을 오름 차순으로 정렬 후

2. target 이라는 변수를 생성하고, target 변수가 매번 반복 하면서, 주어진 동전을 더합니다.

3. 이때, target이 현재 주어진 동전의 금액 보다 작으면, target은 주어진 동전으로는 만들수 없는 금액 입니다.

 

 

3. Java 소스 코드

import java.util.Arrays;

public class Page314 {
    // 만들 수 없는 금액
    public static void main(String[] args) {
        int N = 5;
        int[] moneys = new int[]{3, 2, 1, 1, 9};
        System.out.print(new Page314().solution(N, moneys));
    }

    public int solution(int N, int[] moneys) {
        // 정렬 후
        // 만들 수 없는 금액을 찾았을 때 반복 종료
        Arrays.sort(moneys);

        int target = 1;
        for (int i = 0; i < N; i++) {
            // 만들 수 없는 금액을 찾았을 때 반복 종료
            if (target < moneys[i]) break;
            target += moneys[i];
        }
        return target;
    }
}