[동적 계획법 2 단계] 백준 2293번 동전 1

문제

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

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

입력

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

출력

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

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;
int coin[100];
long long D[10001];
int main() {
	int N, K;
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> coin[i];
	}
	// 0원의 경우는 1가지 
	D[0] = 1;

	//coin[0]로 만들 수 있는 경우의 수를 구하고
	//coin[1] .... 차례로 더하면 coin[0]에 coin[1]을 추가해서 만드는 경우의 수
	//그 이후 쭉쭉 전부 이용해서 만드는 수를 구할 수 있음.

	//단 coin[0]라면 그 이상의 수만 구할 수 있음

	for (int i = 0; i < N; i++)
	{
		for (int j = coin[i]; j <= K; j++)
		{
			D[j] += D[j - coin[i]];
		}
	}
	cout << D[K] << endl;
}