[Gold 5] 2293번 동전 1

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

2293번: 동전 1

 

이 문제는 DP를 통해 해결해야한다.

예제에 따라 동전 3개인 1, 2, 5를 통해 10을 만들려면 아래와 같은 경우의 수가 존재한다.

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 2

1 1 1 1 1 1 2 2

1 1 1 1 2 2 2

1 1 2 2 2 2

2 2 2 2 2

1 1 1 1 1 5

1 1 1 2 5

1 2 2 5

5 5

 

위 경우의 수는 동전 1을 사용할 때 10원을 구하는 경우 1개의 경우의 수가 존재함을 알 수 있다.

동전 2를 사용할 경우 5개의 경우의 수가 존재함을 알 수 있다.

동전 5를 사용할 경우 4개의 경우의 수가 존재함을 알 수 있다.

 

해당 경우의 수에 따라 DP 식을 새우면 dp[N] = dp[N] + dp[N-K]의 식임을 알 수 있다.

쉽게 설명하기 위해 표를 그려 보았다.

 

동전 1을 통해 10을 만드는 경우 

DP[i] += DP[i-1]을 해준다

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

 

동전 2를 통해 10을 만드는 경우

0과 1은 만들 수 없으니 무시한다. 

즉, i = 2부터 DP[i] += DP[i-2]를 해준다.

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

 

동전 5를 통해 10을 만드는 경우

0과 1, 2, 3, 4는 만들 수 없으니 무시한다.

즉, i = 5부터 DP[i] += DP[i-5]를 해준다.

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

 

 

위 표를 따라 정확한 식을 새우게 된다면 아래와 같은 식을 새울 수 있다.

dp[0] = 1;
for (int i = 0; i < N; i++) {
	for (int j = arr[i]; j <= K; j++)
		dp[j] += dp[j - arr[i]];
}

dp[0]을 1로 초기화해 아무 동전도 선택하지 않은 경우를 만든다.

이후 N개의 동전에 대해 K까지의 만들 수 있는 경우의 수를 구한다.

 

#include <iostream> 

using namespace std;

int N, K;
int dp[10001];
int arr[101];
int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dp[0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = arr[i]; j <= K; j++)
			dp[j] += dp[j - arr[i]];
	}
	cout << dp[K] << '\n';
	return 0;
}