[그리디] 이코테 만들 수 없는 금액(Java)

📚 문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

 

예를 들어, N=5이고 동전이 각각 3원, 2원, 1원, 9원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 

또 다른 예시로, N=3이고 동전이 각각 3원, 5원, 7원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1<=N<=1,000)

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

 

입력 예시	출력 예시
5 3 2 1 1 9	8

 

📝 문제 해결

동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하면 된다.

1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 증가시키면 된다.

 

1. 처음에는 금액 1을 만들 수 있는지 확인하기 위해, target = 1로 설정한다.
2. target = 1을 만족할 수 있는지 확인한다. 화폐 단위가 1인 동전으로 금액 1을 만들 수 있다. -> target = 1 + 1 = 2로 업데이트한다.
3. target = 2를 만족할 수 있는지 확인한다. 화폐 단위가 2인 동전이 있다. -> target = 2 + 2 = 4로 업데이트한다.
4. target = 4를 만족할 수 있는지 확인한다. 화폐 단위가 3인 동전이 있다. -> target = 4 + 3 = 7로 업데이트한다.
5. target = 7을 만족할 수 있느닞 확인한다. 이보다 큰 화폐 단위 8인 동전이 있으므로 따라서 금액 7을 만드는 방법은 없다. 따라서 정답은 7이 된다.

 

이러한 원리를 이용하면 단순히 1) 동전을 화폐 단위 기준으로 정렬한 뒤에, 2) 화폐 단위가 작은 동전부터 하나씩 확인하면서 3) target 변수를 업데이트하는 방법으로 최적의 해를 계산할 수 있다.

 

💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        int target = 1;
        for (int i = 0; i < n; i++) {
            if (target < arrayList.get(i)) break;
            target += arrayList.get(i);
        }

        System.out.println(target);
    }
}