백준 2293: 동전 1

문제 요약

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

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

문제 분류

• 다이나믹 프로그래밍

문제 풀이

k원의 동전을 만드는 알고리즘은 대표적으로 그리디 알고리즘이 있지만, 이 문제에서는 해당 알고리즘을 사용할 수 없다.

이 문제의 요는, k + 1원의 동전으로는 k원의 동전을 만들 수 없다는 것이다.
가령 동전 {1, 2, 3}이 있다고 가정하자.
1원으로는 1, 2, 3...k원의 동전을 만들 수 있다.
2원으로는 2, 3...k원의 동전을 만들 수 있다. 1원은 2원보다 작으므로 만들 수 없다.
3원으로는 3.....k원의 동전을 만들 수 있다. 1원과 2원 역시 3보다 작으므로 만들 수 없다.
즉, i원으로는 i, i+1....k원의 동전을 만들 수 있다는 것이다. (단, i <= k)

여기서 동전을 오름차순으로 정렬하고, 각 동전의 가치를 v[i]라고 하자.
v[i]를 사용하여 k원을 만들 때의 경우의 수 dp[k]는 v[i]보다 작은 동전으로만 만드는 경우의 수를 포함한다. 즉, dp[k] += dp[k - v[i]]의 식으로, 누적시키는 꼴이 된다. 이때 i는 0 ~ n의 범위가 된다. 또한 각 k는 v[i]부터 최대 k의 값을 가진다.

그러니깐, 동전을 오름차순 정렬했다는 가정 하에 가장 낮은 가치의 동전부터 순서대로 k원을 만들면 되는데, 사용하는 동전을 추가해나가며 누적해나가는 구조이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[10001];

int main()
{
	int  input, n, k;
	vector<int> v;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		v.push_back(input);
	}
	dp[0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = v[i]; j <= k; j++)
			dp[j] += dp[j - v[i]];
	cout << dp[k];
}