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

 이 문제는 dp를 이용한 문제이다. 처음에는 이 문제를 1원부터 10000원까지 루프를 돌리면서 동전을 루프를 돌려 계산하였는데, 이렇게 하면 순서가 뒤바뀐 경우의 수가 모두 포함되게 된다. 순서가 뒤바뀐 경우를 없애려면 코인에 대해서 루프를 돌리고, 그 안에서 금액에 대한 dp 테이블을 갱신해야 한다. 

 

 주의해야 할 점은 0원을 만드는 경우의 수가 1이라는 것이다. 애초에 이 값을 0으로 해놓으면 값이 제대로 나오지 않는다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 10000

int dp[MAX + 1];

int main() {
	int n, k;
	vector<int> coin;

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int temp;

		cin >> temp;
		coin.push_back(temp);
	}

	dp[0] = 1;

	for (int i = 0; i < coin.size(); i++) {
		for (int j = coin[i]; j <= k; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}

	cout << dp[k] << '\n';

	return 0;
}