[9084] 동전

✔ 동전

[백준 9084]

코드 구현하기

/*
 * 문제 분석하기
 * : 주어진 금액을 만들기 위해 동전들을 조합해 만드는 방법을 모두 세도록 함
 */

/* 
 * 손으로 풀어보기
 * 1. 1원부터 M원까지를 만들 때, 하나의 동전을 사용할 수 있는 경우와 여러 동전을 사용해야 하는 경우에 따른 경우의 수를 세도록 함
 * 2. 금액 M을 만드는 모든 방법의 수를 출력
 */

/*
 * 9084) 동전
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N, M;
    static int[] coins; // coins(동전들을 담은 배열)
    static int[] D; // D(각 동전을 만들 수 있는 방법의 수)

    /*
     * 금액 만들기 준비하기
     */
    static void init(StringTokenizer st) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        coins = new int[N];
        for (int i = 0; i < N; i++) {
            int coin = Integer.parseInt(st.nextToken());
            coins[i] = coin;
        }

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
    }

    /*
     * 금액 만들기
     */
    static void make() {
        D = new int[M + 1];
        for (int i = 0; i < coins.length; i++) {
            for (int j = 1; j <= M; j++) {
                if (j - coins[i] == 0) { // 하나의 동전 종류로만 금액을 만들 수 있다면
                    D[j]++;
                } else if (j - coins[i] > 0) { // 다른 동전 종류와 함께 금액을 만들어야 한다면
                    D[j] = D[j] + D[j - coins[i]];
                }
            }
        }
    }

    /*
     * 금액 M을 만드는 모든 방법의 수를 출력
     */
    static void print() {
        System.out.println(D[M]);
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            init(st);
            make();
            print();
        }
    }
}