[정올 1183] 동전 자판기(下) - JAVA

문제 링크

문제 정의

• $500$, $100$, $50$, $10$, $5$, $1$원 짜리 동전의 개수가 주어짐
• 필요한 금액 $W$가 주어짐
• 지불하지 못하는 경우는 존재하지 않음

동전을 최대로 사용해서 필요한 금액 $W$를 지불하는 방법을 출력

---

접근 방법

초기 접근 방법

최소 동전 수를 구하는 방법은 간단합니다.
큰 동전부터 사용하면 문제를 해결할 수 있습니다.

하지만 반대인 최대 동전 수를 구하기 위해서
최소 동전 수를 활용할 수 있는 방안을 찾아보았습니다.

처음에는 최소 동전 수를 구한 후
동전의 단위를 줄여나가는 방식을 사용하고자 했으나
선택된 동전을 남은 하위 동전들로 만들 수 있을 때까지 반복하는데
단위를 역순으로 500 -> 100 -> 50 -> 10 -> 5 -> 1 한다면
문제를 해결할 수 있다고 생각했습니다.

하지만 구현이 복잡하며 반복되는 로직으로 비효율적일 것이라 생각하고
이 방법은 아니라고 판단해서 포기하게 되었습니다.

최대 동전 수는 직접적으로 구할 수 없고 그러면 최소 동전 수를 활용해 어떻게 해결 가능하지?

최소 동전 수를 활용해 문제를 해결하자는 발상은 맞았지만 접근 방법이 틀렸었습니다.
발상은 떠올리고 나면 아주 단순한데 이 문제의 조건을 보면 이런 조건이 존재합니다.

지불하지 못하는 경우는 존재하지 않음

즉, 항상 해가 존재하며, 그 뜻은 "동전 금액의 총합은 $W$보다 크다" 라는 것입니다.
만약 동전의 총 금액을 $T$라할 때 아래와 같은 발상으로 문제를 해결할 수 있습니다.

W의 최소 동전 수 = 각 동전 수 - (T-W)의 최소 동전 수

조금은 부정확할 수 있지만
$W$의 최소 동전 수로 쓴다면
나머지는 $T-W$의 최대 동전 수가 됩니다.

즉 $W$를 구할 수 있는 $T-W$의 최대 동전 수를 구한다면
총 동전 수에서 $T-W$의 최대 동전 수를 빼주게 된다면
저희가 원하는 $W$의 최소 동전 수를 구할 수 있게 됩니다.

---

코드

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

public class Main {
    static StringTokenizer st;
    static int[] values = {500, 100, 50, 10, 5, 1};
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] available = new int[6];
        int[] usage = new int[6];

        int maxPrice = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 6; i++) {
            available[i] = Integer.parseInt(st.nextToken());
            maxPrice += available[i] * values[i];
        }

        int targetPrice = maxPrice - N;
        for (int i = 0; i < 6; i++) {
            int max = targetPrice / values[i];
            int count = Math.min(max, available[i]);

            usage[i] = count;
            targetPrice -= count * values[i];
        }

        int count = 0;
        for (int i = 0; i < 6; i++) {
            sb.append(available[i] - usage[i]).append(" ");
            count += available[i] - usage[i];
        }

        System.out.println(count);
        System.out.println(sb);
    }
}