동전 자판기(하)

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

public class Main {

    static int[] coinCount = new int[6];
    static int[] coinPrice = {500, 100, 50, 10, 5, 1};
    static int[] answer;

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 6; i++) {
            int amount = Integer.parseInt(st.nextToken());
            coinCount[i] = amount;
        }

        // 1원 ~ 500원짜리 동전 순서대로 시도
        int temp = W;
        int coinIdx = 5;
        answer = new int[6];

        simulate(temp, coinIdx);
        System.out.println(Arrays.stream(answer).sum());
        for (int item : answer) {
            System.out.print(item + " ");
        }
    }

    private static void simulate(int temp, int coinIdx) {
        if (temp == 0 || coinIdx < 0) {
            return;
        }
        for (int i = coinCount[coinIdx]; i >= 0; i--) {
            if (coinIdx == 0) {
                if (temp - i * coinPrice[coinIdx] == 0) {
                    answer[coinIdx] = i;
                }
                continue;
            }
            if ((temp - i * coinPrice[coinIdx]) % coinPrice[coinIdx - 1] == 0) {
                answer[coinIdx] = i;
                simulate(temp - i * coinPrice[coinIdx], coinIdx - 1);
                break;
            }
        }
    }
}

G2

이전까지 자판기 문제라 하면 W원을 만들기 위해 필요한 가장 적은 수의 동전 류 라고 할 수 있겠다.

근데 이 문제는 가능한 많은 수의 동전을 사용해야 하는 문제이다.

그래도 달라질 건 없다.

각 동전의 금액이 서로의 배수, 약수 관계이기 때문에,
금액이 적은 동전부터 시작해서 최대한 사용하고 또 다음 큰 금액의 동전으로 넘어가서 같은 로직을 실행하면 되는 아이디어이기 때문이다.

다만 재귀를 타고 들어가기 때문에, 종료 조건만 잘 적어주면 금방 통과할 수 있는 문제다.

출처: https://www.jungol.co.kr/problem/1183