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

문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.
예를 들어, N=5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.
또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

---

입력 조건

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

---

출력 조건

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

---

알고리즘

 

책의 알고리즘은 아래와 같다.

 

1. 화폐 단위를 기준으로 오름차순으로 정렬한다.
2. 1부터 차례대로 특정한 금액(target)을 만들 수 있는지 확인한다.
3. 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정한다.
4. 화폐 단위가 작은 순서대로 동적을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인한다.
5. 만약 target 금액을 만들 수 있다면, target 값을 업데이트하는 방식을 이용한다.

 

그렇다면 두가지 의문이 생길 것이다.

 

'현재 확인하는 동전을 이용해 target 금액을 만들 수 있는 조건이 무엇인가?'
'target은 어떤 방식으로 업데이트하는가?'

 

이 의문에 대한 답은 아래와 같다.

 

현재 확인하는 동전을 이용해 target 금액을 만들 수 있는 조건

기존 target 값 >= 현재 확인하는 동전 값

 

target 업데이트 방식

기존 target 값 + 현재 확인하는 동전 값

 

그 이유에 대해 알아보자.

 

i) 기존 target 값 < 현재 확인하는 동전 값

기존 target 값이 8, 현재 확인하는 동전 값이 10이라고 가정하자.

기존 target 값이 8이므로 1~7까지 만들 수 잇다.

현재 확인하는 동전 값 10을 이용하면 10~17을 만들 수 있으므로 기존 target 값인 8을 만족시킬 수 없다.

즉, 8이 결과 값이 된다.

 

ii) 기존 target 값 == 현재 확인하는 동전 값

기존 target 값이 10, 현재 확인하는 동전 값이 10이라고 가정하자.

기존 target 값이 10이므로 1~9까지 만들 수 잇다.

현재 확인하는 동전 값 10을 이용하면 10~19을 만들 수 있으므로 기존 target 값인 10을 만족한다.

target 값은 20(기존 target 값 10 + 현재 확인하는 동전 값 10)으로 업데이트 하면 된다.

 

iii) 기존 target 값 > 현재 확인하는 동전 값

기존 target 값이 10, 현재 확인하는 동전 값이 8이라고 가정하자.

기존 target 값이 10이므로 1~9까지 만들 수 있다.

현재 확인하는 동전 값인 8을 이용한다면 8~17을 만들 수 있으므로 기존 target 값인 10을 만족한다.

target 값은 18(기존 target 값 10 + 현재 확인하는 동전 값 8)으로 업데이트 하면 된다.

---

코드 - Java

import java.util.*;

public class Main {

    public static  int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

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

        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);
    }
}

 

 

참고

[이코테-그리디] 기출 - 04. 만들 수 없는 금액