[2293/DP] 동전 1 (JAVA)

문제

링크: https://www.acmicpc.net/problem/2293

---

풀이

1원부터 k원까지 단계적으로 추가해가면서 최종값을 구해야 겠다는 생각은 금방 들었는데, 그 안에서 동전도 단계적으로 추가해야 겠다는 생각을 하는 데에 시간이 조금 걸렸다.

 

모든 동전을 다 사용하는 경우의 수를 한 번에 구하는 것은 불가능하다. 따라서 사용하는 동전을 제한하고 하나씩 늘려감으로써 최종 값을 구해야 한다.

 

즉, 동전 하나(coins[1])만 사용했을 때, 1원부터 k원까지 전체 value를 만들 수 있는 경우의 수를 구하고,

동전 두개(coins[1], coins[2])를 사용했을 때, 2원부터 k원까지의 경우의 수를 구해야 한다.

이렇게 전체 동전을 사용할 때까지 반복하면 모든 동전을 사용했을 때 k원을 만들 수 있는 경우의 수를 구할 수 있다.

 

각 변수에는 다음을 저장한다.

- coins[i] : i번째 동전의 value

- dp[i] : 동전 조합으로 i원을 만드는 경우의 수

 

i번째 동전을 사용했을 때의 경우의 수는 dp[전체 value - i번째 동전의 value]와 같다. 이 때, dp[0] = 1로 초기화해주어야 한다. 전체 value가 i번째 동전의 value와 같은 경우 coins[i] 1개를 사용하는 경우이기 때문에 경우의 수를 증가시켜 주는 것이다.

 

이를 코드로 표현한 2중 for문에서 i는 사용할 동전의 개수 (즉, 1번부터 i번째까지)이고, j는 전체 value를 의미한다.

dp[j]는 기존의 경우의 수 + i번째 동전을 추가로 사용했을 때 경우의 수로 업데이트한다.

---

코드

// 백준 2293 '동전 1'
// DP
// 2020.08.15

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

public class Main {

    static int n;
    static int k;
    static int[] coins = new int[101];
    static int[] dp = new int[10001];

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

        // Get inputs
        StringTokenizer tk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(tk.nextToken());
        k = Integer.parseInt(tk.nextToken());

        for (int i = 1; i <= n; i++) {
            tk = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(tk.nextToken());
        }

        // Get result
        dp();

        // Print output
        bw.write(Integer.toString(dp[k]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
    }
}