동전 1 (feat. 백준, 2293번)

동전 1
https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

반응형

 

// woohyeon.kim
// https://www.acmicpc.net/problem/2293
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, K, arr[101] = { 0 }, dp[10001] = { 0 };
	dp[0] = 1;
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	for (register int i = 1, j; i <= N; ++i)
		for (register int j = arr[i]; j <= K; ++j)
			dp[j] += dp[j - arr[i]];
	cout << dp[K] << endl;
	return 0;
}
// *&)*@*

N=3, K=10, 동전=2,3,4 라고 가정해 보겠습니다.

처음 동전 2원으로 1원 ~ 10원까지 만들수 있는 총 개수를 구해보겠습니다.

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

다음 동전 3원을 추가해서 1원 ~ 10원까지 만들수 있는 총 개수를 구해보겠습니다.

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

빨간색 글씨가 있는 부분들의 값이 변경 되었음을 알수 있습니다.

5원을 만들기 위해서는 기존 2원으로는 불가능했지만 3원이 추가됨으로써 가능하게 됩니다. 다만 2원도 필요하기 때문에 2원의 결과가 더해졌습니다.

6원을 만들기 위해서는 기존 2원으로는 1번이 가능했지만 3원이 추가됨으로써 2원+3원 조합이 가능하게 되었습니다. 따라서 3원의 결과가 더해졌습니다.

즉, 각각의 동전에 대해서 원하는 값의 총 가능 개수 = 원하는 값의 총 가능 개수 + (원하는 값 - 현재의 동전값)의 총 가능 개수. 즉, Pk의 총 가능 개수 = Pk의 총 가능 개수 + P(k-현재의 동전값)의 총 가능 개수 가 되게 됩니다.

마지막으로 4원을 추가해서 1원 ~ 10원까지 만들수 있는 총 개수를 구해보겠습니다.

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

따라서 P10 = 5 가 되게 됩니다.