[백준 2293] 동전1 (C++)

문제 출처 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

다이나믹 프로그래밍으로 풀었다.

 

int n, k;
cin >> n >> k;
vector<int> coin(n + 1, 0);
vector<int> dp(k + 1, 0);
dp[0] = 1;

n과 k를 입력 받고 사이즈에 맞게 vector를 선언해준다.

coin은 n개의 동전 값을 받아 저장하고, dp는 금액을 만들 수 있는 방법의 수를 저장할 것이다.

dp[0]이 1인 이유는 0원을 만드는 방법은 아무것도 사용하지 않는 한가지 방법만 있기 때문이다.

 

for (int i = 0; i < n; i++) {
	cin >> coin[i];
}
for (int i = 0; i < n; i++) {
	for (int j = coin[i]; j <= k; j++) {
		dp[j] += dp[j - coin[i]];
	}
}
cout << dp[k];

동전의 가치를 입력 받고 2중 for문을 통해 각각의 동전마다 다이나믹 프로그래밍을 수행한다.

dp[j] += dp[j - coin[i]]는 j원을 만들 수 있는 방법의 수 dp[j]를 계산하는 것이다.

coin[i]는 현재 다이나믹 프로그래밍을 수행하는 동전의 가치이다.

j - coin[i]는 현재 만드려하는 j원에서 코인의 가치를 뺀 것으로 j - coin[i]를 만드는 방법의 수 dp[j - coin[i]에 coin[i]를 추가하면 j를 만드는 방법의 수가 되는 것이다.

 

예시와 같이 3 10 1 2 5를 입력했다고 했을 때

dp: 1 0 0 0 0 0 0 0 0 0 0 (index는 목표하는 금액을 의미합니다.)

초기에는 위와 같은 상태이다.

 

 

dp: 1 1 1 1 1 1 1 1 1 1 1

1원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

 

dp: 1 1 2 2 3 3 4 4 5 5 6

2원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

예를 들어 2원을 만드는 방법에는 1원 2개를 쓰는 방법과 2원 1개를 쓰는 방법, 총 2가지가 있을 것이다.

3원을 만드는 방법에는 1원 3개를 쓰는 방법과 2원 1개, 1원 1개를 쓰는 방법, 총 2가지가 있을 것이다.

4원을 만드는 방법은 2원을 만드는 방법인 1원2개, 2원 1개에서 2원을 추가하여 (1, 1, 2), (2, 2)와 1원만을 사용한 (1, 1, 1, 1) 총 3가지 방법이 있을 것이다.

위와 같이 j원을 만드는 방법은 현재 저장되어 있는 j원을 만드는 방법의 수에서 j - coin[i]을 만드는 방법의 수를 더해 나가면 구할 수 있다.

 

dp: 1 1 2 2 3 4 5 6 7 8 10

5원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

 

모든 동전에 대해 다이나믹 프로그래밍을 수행했다면 k원을 만드는 방법의 가지 수인 dp[k]를 출력해준다.

 

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	vector<int> coin(n + 1, 0);
	vector<int> dp(k + 1, 0);
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = coin[i]; j <= k; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[k];
	return 0;
}

전체코드

 

알고리즘

- 다이나믹 프로그래밍