[코딩테스트]BJ2293번 동전1-C++

[문제]

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

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

[입력]

첫째 줄에 N,K 가 주어진다. (1<=N<=100, 1<=K<=10,000) 다음 N개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

[예제 입력 1]

3 10
1
2
5

[예제 출력 1]

10

[접근 방식]

DP 알고리즘을 이용한다.

예제를 생각해보면 동전 1원으로 1원~10원까지 만드는 경우를 생각해본다.
모두 1가지일 것이다.
2원을 추가해서 생각해본다. 2원으로 만들 수 있는 개수는 1원을 만든 것에서 짝수가 되는 개수로 증가 한다.
가령, 2원을 만드는 경우는 1을 이용해서 1가지 , 2를 1개 쓰는 경우 하여 2가지 일 것이다. 4를 만드는 경우는 2원을 만든 2가지에서 +1 하여 3가지이다.
이를 수식으로 표현하면, num_coins[j]= num_coins[j-arr[i]] 라는 수식이 나온다.
코인의 개수를 뺀 만큼의 값은 앞선 동전으로 구한 개수를 이용하는 것이다. 이것이 dynamic programming의 원리이다.

[코드]

#include<iostream>
using namespace std; 

int main() {
	int arr[100] = { 0, };
	int num_coins[10001] = { 0, };
	int n, k; 
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	num_coins[0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = arr[i]; j <= k; j++) {
			num_coins[j] += num_coins[j - arr[i]];
		}
	}
	cout << num_coins[k] << endl;

	return 0;
}