문제

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

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

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

---

입력

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

---

출력

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

---

풀이

접근방법

시간제한 0.5초, 메모리 4MB이다.
(1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

시간제한을 보고 동적계획법이 떠올라야 한다.
어떻게 접근해야 할 것인지 생각을 해보자.

예시로 한 번 생각을 해보자.

3 10
1
2
5

동적계획법의 기본은 계산했던것을 다시 계산하지 않고, 이전에 구한 값을 재사용해야한다. 어떤 값을 재사용할 수 있을까?

1원 만들기 : 1원을 1개 사용
2원 만들기 : 1원을 2개 사용 또는 2원을 1개 사용
.
.
.

이렇게 생각하면 규칙을 찾기가 모호하다.

조금 다르게 생각을 해보자.

가진 동전 (1, 2, 5)
0원 만들기 : 하나도 사용하지 않기.
1원 만들기 : 0원 만드는 방법의 수 + 1원을 사용하는 방법 1개
2원 만들기 : 1원 만드는 방법의 수 + 1원 사용, 0원 만드는방법의 수 + 2원 사용
.
.
.

즉, dp로 각 금액을 만드는 방법의 수를 기록해두고 재사용할 수 있다.
위의 설명을 조금 더 정리해보자면,

dp[i] : i원을 만드는 방법의 수, coin[i] : i번째 입력으로 주어진 동전
가진 동전 (1, 2, 5)

dp[0] = 1
dp[1] = dp[0]+1원사용
dp[2] = dp[1]+1원사용, dp[0]+2원사용

=>

dp[k] = dp[k] + dp[k-coin[i]]

아래와 같은 수식을 구할 수 있다.

---

코드

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

public class Main {
	static int N, K;
	static int[] coin, dp;

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

		String[] splitedLine = in.readLine().split(" ");
		N = stoi(splitedLine[0]);
		K = stoi(splitedLine[1]);

		coin = new int[N];
		dp = new int[K + 1];
		for (int i = 0; i < N; ++i)
			coin[i] = stoi(in.readLine());

		dp[0] = 1; // 0원을 만들기 위해서는 아무동전도 안쓰는 방법 1개가 존재함.
		for (int i = 0; i < N; ++i) { 
			for (int j = coin[i]; j <= K; ++j) {
				dp[j] += dp[j - coin[i]];
			}
		}
		System.out.println(dp[K]);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}