[Java] 2293. 동전 1

www.acmicpc.net/problem/2293

2293번: 동전 1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

---

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

public class BOJ_2293 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int input[] = new int[n];
		int dp[][] = new int[n + 1][k + 1];
		for (int i = 0; i < n; i++) {
			int tmp = Integer.parseInt(in.readLine());
			input[i] = tmp;

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

				if (j < current)
					dp[i][j] = dp[i - 1][j];
				else
					dp[i][j] = dp[i][j - current] + dp[i - 1][j];
			}
		}
		System.out.println(dp[n][k]);
	}

}

0/1 knapsack과 동일한 방법으로 문제를 해결하였다.

 

DP로 해결했기 때문에 다음과 같은 점화식이 유도되었다.

여기서 C(i)는 i번째로 고려할 코인의 가치이고, D(i, k)는 i번째 코인까지 사용해서 k를 만들 수 있는 경우의 수이다.