BOJ#9084 동전

BOJ#9084 동전

* 문제

https://www.acmicpc.net/problem/9084

* 풀이

참고한 블로그 : 

http://wootool.tistory.com/177

http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220793012348

http://heygyun.tistory.com/46

동적계획법의 개념(복잡한 문제를 여러 하위 문제로 나누어 푼다)을 잘 생각해봅시다.

dp[i] : 주어진 동전을 가지고 금액 i를 만드는 경우의 수

예를 들어 목표 금액이 30원이고, 동전이 5원, 10원짜리가 있을 때

일단은 5원짜리만 있다고 가정했을 때 dp[30] : 5원짜리로 30원을 만드는 경우의 수

이제 10원짜리 동전을 추가해보자. 

dp[30] : 30원을 만드는 경우의 수 = 기존의 경우의 수(5원짜리 동전으로만) + 10원짜리 동전을 하나 추가한 경우

dp[30] = dp[30] + dp[30 - 10] = dp[30] + dp[20]

dp[20] : 20원을 만드는 경우의 수 = 기존의 경우의 수(5원짜리 동전으로만) + 10원짜리 동전을 하나 추가한 경우

dp[20] = dp[20] + dp[20 - 10] = dp[20] + dp[10]

dp[10] : 10원을 만드는 경우의 수 = 기존의 경우의 수(5원짜리 동전으로만) + 10원짜리 동전을 하나 추가한 경우

dp[10] = dp[10] + dp[10 - 10] = dp[20] + dp[0]

(여기서 dp[0] = 1)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/7005cb6086b30d19d0be4ffd3bbf519589a3711f/BOJ%239084_Coin/src/Main.java

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

/**
 * BOJ#9084 동전
 * https://www.acmicpc.net/problem/9084
 */

public class Main {

    public static void main(String[] argS) throws IOException {

        int N;
        int M;
        int[] coin;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {

            N = Integer.parseInt(br.readLine());
            coin = new int[N];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {

                coin[i] = Integer.parseInt(st.nextToken());
            }

            M = Integer.parseInt(br.readLine());

            int[] dp = new int[M + 1];
            Arrays.fill(dp, 0);

            dp[0] = 1;
            for (int i = 0; i < N; i++) {
                for (int j = coin[i]; j <= M; j++) {

                    dp[j] += dp[j - coin[i]];
                }
            }

            System.out.println(dp[M]);

        } // ~ testcase loop
    }

}