[백준 9084 : JAVA] 동전 / DP

문제

---

 

 

 

풀이

---

점화식을 어떻게 세워야할까 노트에 표를 그려보면서 고민을 해봤지만... 결국 풀이를 참고하였다.

 

문제를 단순화하여, 동전의 종류가 한 가지일 때를 생각해보자.

예를 들어, 동전의 종류 A = {2} 이고, 만들어야하는 수 K = 10 이라고 해보자.

 

2원짜리 동전으로 10원을 만들려면 어떻게 해야할까? (2*5=10 이니까 1가지겠네 뭐.. 라고 생각하셨다면 우리 DP 공부 열심히 합시ㅏ..)

이때, 구하고자하는 타겟인 10을 바로 생각하지 말고, 타겟을 기준으로 1부터 생각해보는 것이다.

 

2원짜리 동전으로 1원을 만드는 경우의 수는?

2원짜리 동전으로 2원을 만드는 경우의 수는?

2원짜리 동전으로 3원을 만드는 경우의 수는?

2원짜리 동전으로 4원을 만드는 경우의 수는?

... (중략)

2원짜리 동전으로 10원을 만드는 경우의 수는?

 

가지고있는 동전의 수보다 작은 수는 만들 수 없으니 만들고자 하는 수가 2원일 때부터 생각해보자. (cache[i]는 i원을 만드는 경우의 수)

2원짜리 동전으로 2원을 만들려면 --> 0원 + 2원짜리 동전

2원짜리 동전으로 3원을 만들려면 --> 1원 + 2원짜리 동전  --> cache[3] = cache[1]

2원짜리 동전으로 4원을 만들려면 --> 2원 + 2원짜리 동전  --> cache[4] = cache[2]

2원짜리 동전으로 5원을 만들려면 --> 3원 + 2원짜리 동전  --> cache[5] = cache[3]

 

즉, cache[i] = cache[i - 2]  라는 점화식이 나온다.

 

 

 

코드

---

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

public class Main {

    private static int T, N, M;
    private static int[] arr, cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            M = Integer.parseInt(br.readLine());

            cache = new int[M + 1];
            cache[0] = 1;
            for (int coin : arr) {
                for (int j = coin; j <= M; j++) {
                    cache[j] += cache[j - coin];
                }
            }

            sb.append(cache[M]).append("\n");
        }

        System.out.println(sb.toString());
    }
}