[Java] 9084번: 동전 Gold 5

문제 링크

일단 점화식은 이렇다.

DP[i] = DP[i] + DP[i-coin]

이것을 각 동전들마다 모두 실행해주면 되는 것이다.

단 주의할 점은 금액이 작은 동전부터 실행해야 한다는 것이다!

왜냐하면 금액이 작은 동전들부터 고려해야 가능한 모든 케이스를 세어볼 수 있고,
그 결과에 금액이 큰 동전을 다시 고려해서 가능한 케이스를 고려할 수 있다.

간단하게 예시로 생각해보면 이해가 쉬울 것이다.
20원을 만드는 경우를 생각해보자.

10원부터 고려를 했다면,
기존에 10원을 만들 수 있는 케이스는 10원 하나 밖에 없었기에
10원에 10원을 한 번 더 사용한 케이스밖에 생각할 수 없었을 것이다.

그러나 1원 5원 10원순으로 고려했다면 10원을 만들 수 있는 케이스는

1111111111
111115
55
10

이렇게 네 가지가 이미 존재했을 것이다.
여기에 10원을 한 번 더 사용해서 총 네가지를 모두 고려할 수 있다.
그렇기에 작은 금액부터 큰 금액순으로 고려해야한다.

정답

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            // 동전 입력 받기
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] coins = new int[N];
            for (int i = 0; i < N; i++) {
                coins[i] = Integer.parseInt(st.nextToken());
            }

            // 목표 금액 입력 받기
            int target = Integer.parseInt(br.readLine());
            int[] dp = new int[target + 1];
            dp[0] = 1; // 자기 자신의 금액을 만드는 케이스

            // DP
            for (int coin : coins) {
                for (int i = coin; i <= target; i++) {
                    dp[i] += dp[i - coin];
                }
            }

            // 출력
            System.out.println(dp[target]);
        }
    }
}