[BOJ 6126 // C++] Cow Cash

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6126번 문제인 Cow Cash이다.
문제는 아래 링크를 확인하자.

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

6126번: Cow Cash

각 동전의 액수를 v1, v2, ... 등으로 표현하자.

 

dp[k][i]를 v1, ..., vk의 동전들을 이용해 금액 i를 만들 수 있는 경우의 수라 하자.

 

각 금액을 만드는 방법은 1) 동전 vk를 하나 이상 사용했거나 2) 동전 vk를 사용하지 않고 i의 금액을 만든 경우 둘로 나눌 수 있다.

 

1) vk를 하나 이상 사용한 경우들을 생각해보자. 이 케이스에 속하는 모든 각 경우는 동전 vk를 하나 이상 포함하고 있으므로 각 케이스와 그 케이스에서 vk를 하나씩 뺀 케이스는 일대일 대응이 됨을 알 수 있다. 그 경우의 수는 dp[k][i-vk]와 같다.

2) vk를 사용하지 않은 경우들을 생각해보자. 이 케이스의 모든 각 경우는 금액 i를 v1, ..., v(k-1)로 구성하는 경우들과 정확히 대응된다. 따라서 이러한 경우들의 가짓수는 v[k-1][i]와 같다.

 

위의 내용을 이용하여 점화식을 세우고 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M;
ll ans[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ans[0] = 1;

	cin >> M >> N;
	while (M--) {
		int x; cin >> x;
		for (int i = x; i <= N; i++) ans[i] += ans[i - x];
	}

	cout << ans[N];
}