[c++/백준] 2293번: 동전 1*

문제 링크

2293번: 동전 1

풀이

동전 n개를 한 번에 계산하려니까 안 풀린 문제.. 하나씩 생각해야 한다.

1. dp에는 해당 인덱스만큼 값을 동전으로 만들 수 있는 경우의 수이다. 즉 dp[k]는 답이 된다.
2. dp[0]은 값이 0이므로 아무것도 넣지 않는 경우의 수 1
3. 동전이 값보다 크면 해당 동전은 넣지 못하므로 continue
   3-1. 아니면, dp[j-arr[i]]를 더해준다.
   동전 3으로 값 5를 만든다고 하면, dp[5-3]. 즉, 값 2인 경우의 수에서 동전 3을 하나 더해주면 만들 수 있기 때문에 dp[j-arr[i]] 값을 더해주는 것이다.
4. dp[k]를 출력하면 끝.

코드

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int n, k;
	cin >> n >> k;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	vector<int> dp(k+1);
	dp[0] = 1; // 하나도 안 넣는 경우의 수

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (arr[i] > j) continue;
			dp[j] += dp[j - arr[i]];
		}
	}

	cout << dp[k] << endl;

	return 0;
}