[Java] BOJ 9084번 동전

9084번: 동전

---

풀이

DP를 사용하여 해결했습니다.

문제에서 주어진 수는 너무 큰 관계로 3개의 동전 2원, 3원, 5원으로 10원을 만드는 경우를 구해보겠습니다.

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

2원의 경우 위와 같은데 이때, 총경우의 수를 구해야 하므로 구한 결괏값을 그대로 유지하고 새로 갱신을 해나가야 합니다.

다음으로 3원의 경우를 보겠습니다.

예를 들어, 3원의 경우 앞서 2원으로 만들 수 있는 경우의 수들이 저장되어있기 때문에 이를 활용해서 만약 5원을 만든다면 5 - 3 = 2 즉, 2원을 만드는 경우의 수에 3원을 더하면 5원이 되므로 2원을 만드는 경우의 수를 현재 M원의 경우의 수에 더 해주면 됩니다.

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

마지막으로 5원의 경우는

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

와 같이 되므로 모든 동전에 대해서 경우의 수를 구했으므로 10원을 만드는 경우의 수는 4가 됩니다.

 

자세한 내용은 코드의 주석을 참고하시면 이해하시는데 도움이 됩니다.

---

코드

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

public class Main {
	public static int T, N, money;
	public static int[] coins;
	public static int[] memo;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		while (T-- > 0) {
			N = Integer.parseInt(br.readLine());
			
			// 동전들을 저장한다.
			coins = new int[N];
			// 문제에서 최대로 구할 수 있는 돈은 10000원 까지임
			memo = new int[10001];
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; ++i) {
				coins[i] = Integer.parseInt(st.nextToken());
			}
			
			// 문제에서 구하고자하는 금액
			money = Integer.parseInt(br.readLine());
			
			for (int i = 0; i < N; ++i) {
				// 조사하고자하는 동전의 금액보다 작은 액수는 만들 수 없으므로
				// 현재 동전의 금액을 시작으로 구하고자하는 금액을 만드는 경우를 구한다.
				// 동전의 금액 한개도 동전의 금액을 만들 수 있는 경우이므로 1을 더한다.
				memo[coins[i]] += 1;
				for (int j = coins[i]; j <= money; ++j) {
					// 현재 금액 j 에서 현재 동전의 금액 coins[i]를 뺀 금액을 만드는 경우의 수를
					// 현재 금액 j의 경우에 수에 더해준다.
					memo[j] += memo[j - coins[i]];
				}
			}
			
			System.out.println(memo[money]);
		}
	}
}

---

pyo7410/Algorithm