[이코테][Java] 만들 수 없는 금액

문제 설명

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

 

입력조건

• 첫째 줄에 동전의 개수를 나타내는 양의 정수 N(1 <= N <= 1,000)
• 둘째 줄에 각 동전의 화폐단위를 나타내는 N개의 자연수

출력조건

• 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값

입출력 예시

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

 

 

 

 

문제 풀이

• 입력받은 n개의 동전들을 오름차순 정렬한 후, 동전들로 1부터 차례대로 특정 금액(target)을 만들 수 있는지 확인한다.
• target >= (현재 동전금액) 일 경우, 현재 동전으로 target을 만들 수 있다 → target 값 업데이트
• 여기서 target이 특정 값일 때, 1 ~ (target-1)까지의 모든 금액을 만들 수 있다고 가정한다.

 

예시) n=5, {3, 2, 1, 1, 9}

동전을 오름차순 정렬하면 {1, 1, 2, 3, 9}이다.

오름차순 정렬한 동전을 순서대로 확인하면서 특정 금액 target을 만들 수 있는지 확인한다.

1) target = 1, coin = 1

• coin 1원이 추가되어 1원을 만들 수 있다. → 1 == 1
• target = target + coin = 1 + 1 =2 로 업데이트
• 현재 가지고 있는 동전 {1}

2) target = 2, coin = 1

• 이전 단계를 통해 현재 가지고 있는 동전으로 1원까지 만들 수 있다. 
• coin 1원이 추가되어 1, 2원을 만들 수 있다. → 2 > 1
• target = target + coin = 2 + 1 = 3 으로 업데이트
• 현재 가지고 있는 동전 {1, 1}

3) target = 3, coin = 2

• 이전 단계를 통해 현재 가지고 있는 동전으로 1 ~ 2원까지 만들 수 있다.
• coin 2원이 추가되어 1, 2, 3, 4원을 만들 수 있다. → 3 > 2
• target = target + coin = 3 + 2 = 5 으로 업데이트
• 현재 가지고 있는 동전 {1, 1, 2}

3) target = 5, coin = 3

• 이전 단계를 통해 현재 가지고 있는 동전으로 1 ~ 4원까지 만들 수 있다.
• coin 3원이 추가되어 1, 2, 3, 4, 5, 6, 7 원을 만들 수 있다. → 5 > 3
• target = target + coin =  5 + 3 = 8 으로 업데이트
• 현재 가지고 있는 동전 {1, 1, 2, 3}

4) target = 8, coin = 9

• 이전 단계를 통해 현재 가지고 있는 동전으로 1 ~ 7원까지 만들 수 있다.
• coin 9원이 추가되어 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16 원을 만들 수 있다. → 8 < 9

따라서 만들 수 없는 최소값은 8이 된다.

import java.io.*;
import java.util.*;

public class Main1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());    //동전의 개수
        ArrayList<Integer> coins = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            coins.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(coins);

        int target = 1;
        for (int i = 0; i < coins.size(); i++) {
            if (target < coins.get(i)) {	//target이 coin보다 작으면 target을 만들 수 없다.
                break;
            } else {	//target이 coin보다 크거나 같으면 target을 만들 수 있으므로 target 업데이트
                target += coins.get(i);
            }
        }

        bw.write(target + "\n");
        bw.flush();
        bw.close();
    }
}

---

[참고]

- 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

- https://kk-programming.tistory.com/11

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