2293 - 동전 1

문제: boj.kr/2293
날짜: 09/22 (일)
성공여부: X

 

1, 2, 5원 동전을 갖고 10원을 만든다고 하면 1원만 써서 만드는 경우의 수, 1원과 2원을 써서 만드는 경우의 수, 1원 2원 5원을 모두 사용해서 만드는 경우의 수로 나눌 수 있다. 1원을 먼저 써서 만드는 경우의 수를 구해놓고 2원을 써서 만드는 경우의 수를 더하면 1원과 2원으로 10원을 만드는 경우의 수를 찾을 수 있지 않을까?

 

그럼 중복은 어떻게 제거하냐? 1원으로만 2원부터 10원까지 만든 경우의 수가 있는 상황에서 2원을 무조건 투입한다고 생각해보자. 그럼, 2원으로 2원을 만들기 위해 2원 하나만 사용할 수 있다. 1+1, 2 2가지가 있는 경우이므로 원래 1+1 경우의 수에 2로 만든 경우의 수 = 2가 된다.

 

3원의 경우 1+1+1은 원래 있었고 2원이 투입되면 1+2가 있다. 이는 1원으로 1원을 만든 경우의 수에 2원만 붙여주면 되니까 결국, 1원으로 1원을 만든 경우의 수를 추가로 더하면 된다. 2+1도 있지않냐고 할 수 있지만, 2원으로 2원을 만든 경우의 수에 1원을 추가로 더한 것인데 우리는 항상 마지막에 2원을 사용할거기 때문에 생각하지 않아도 된다.

4원의 경우 1+1+1+1 경우의 수를 구한 상태이고, 추가로 1+1+2와 2+2 경우의 수가 있다. 이는 1로 2를 만드는 경우의 수와 2로 2를 만드는 경우의 수 즉, 1원과 2원으로 2원을 만드는 경우의 수 + 1원으로 4원을 만든 경우의 수가 된다.

 

계속 이런식으로 나아가면 다음과 같은 테이블이 완성된다.

 

dp	0	1	2	3	4	5	6	7	8	9	10
1원	1	1	1	1	1	1	1	1	1	1	1
2원	1	1	2	2	3	3	4	4	5	5	6
5원	1	1	2	2	3	4	5	6	7	8	10

 

즉, 1원만 써서 만든 경우의 수에 2원을 추가 투입해보고, 5원을 추가 투입해보는 것이다. 이럼 중복없이 모든 경우의 수를 구할 수 있다. 왜냐면 위에 말했듯이 무조건 추가 투입한 동전을 마지막에 사용하도록 하기 때문이다.

 

 

코드

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

public class Main {

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        dp = new int[k+1];

        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int tmp = Integer.parseInt(br.readLine());
            if (tmp > 10000) continue;
            for (int j = tmp; j <= k; j++)
                dp[j] += dp[j - tmp];
        }

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