[BOJ] 2293 동전 1 java

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

풀이

 

package footdev._5주차;

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

public class BOJ_동전_1 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int n, k;
    static int[] coins, dp;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        coins = new int[n];
        dp = new int[k + 1];
        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        //로직
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = 1; i <= k; i++) {
                if (i - coin >= 0) {
                    dp[i] += dp[i - coin];
                }
            }
        }

        System.out.println(dp[k]);
    }
}

 

DP 문제이고 점화식 도출이 생각이 안났기에 빠르게 풀이를 본 문제이다. 

 

일단 DP로 풀어야 하는 문제라고 판단을 내리면, 일차적으로 표를 만들어 도식화를 하면 규칙을 찾기 수월해진다.

 

문제의 목표는 '주어진 동전들을 이용해 k값을 만들 수 있는 모든 경우의 수를 찾아라.' 이다.

 

그렇다면 1 ~ k까지 주어진 동전들을 이용해서 만들 수 있는 경우의 수를 표로 만들어서 세어본다.

 

n	1	2	3	4	5	6	7	8	9	10
1원	1	1	1	1	1	1	1	1	1	1
1,2원	1	2	2	3	3	4	4	5	5	6
1,2,5원	1	2	2	3	4	5	6	7	8	10

 

 

다음과 같이 표를 만들 수 있다. 여기서 잘 보면 규칙이 있다는 것을 알 수 있다.

 

 

dp[n] += dp[n - coins[i]] 가 점화식으로 도출되는 것 이다.

 

그리고 이걸 구현할 때 보면 다른 규칙이 한가지 더 있는데 동전이 한개 추가될 때 마다 값이 갱신되는 시점이 dp[동전가치] 부터 값이 갱신되는 것을 볼 수 있다. 그냥 구현하면 index 에러가 뜰 수 있기 때문에 이 부분을 이용하면 쉽게 구현을 할 수 있다.