백준 No.2293) 동전 1

경우의 수의 문제이다.

이런 경우의 수의 경우, 처음부터 마지막 값까지 가면서 누적되는 경우의 수를 더해가며 구하게 된다.

왜냐하면 1. 목표값까지의 경로값의 경우의 수는 불변하며, 2. 다음 목표값은 이전의 경로값과 중복되기 때문이다.

 

예를 들어보자

 

동전 1, 2, 5,가 있고 무한하게 주어진다고 가정하자

 

여기서 총합 2COIN을 만든다면

1+1, 2

이렇게 2개의 경우의 수가 나오게 되며 이는 COIN의 종류가 변하지 않는 이상 불변한다. (1)

 

 

여기서 COIN을 만든다면

1+1+1, 2+1

이렇게 2개의 경우의 수가 된다.

 

여기서 3COIN의 경우의 수를 자세히 보게 되면

2COIN을 만드는 경우의 수에 1COIN을 더한 값이 나온다.

즉 기존의 경우의 값을 참조하여 새로운 경우의 값을 구하는 것이다.(2)

 

 

이렇게 계산해본다면

$dp[0] = 1$

$dp[n] = \sum(dp[n - COIN(x)])$ 

의 식이 나오게 된다.

 

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

class Main{

    public static void main(String[] args) {
        Coin1 qz = new Coin1();
        qz.run();
    }
}

class Coin1{
    private int[] dp;
    private int[] coin;

    public void run() {

        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] tmp = br.readLine().split(" ");

            int n = Integer.parseInt(tmp[0]);
            int k = Integer.parseInt(tmp[1]);

            dp = new int[k+1];
            coin = new int[n];


            for (int i =0; i< n ; i++) {
                coin[i] = Integer.parseInt(br.readLine());
            }

            dp[0] = 1;

            for(int i = 0 ; i < n ; i++ ) {
                for (int j = coin[i] ; j <= k ; j++) {
                    dp[j] += dp[j - coin[i]];
                }
            }

            System.out.println(dp[k]);
        }catch (IOException e) {
            System.out.println("Input Error");
            System.out.println(e.getMessage());
        }
    }
}