[백준 c++] 2293 동전 1

문제

https://www.acmicpc.net/problem/2293
각각 다른 가치를 가진 동전 n개를 개수와 상관없이 사용해서
합이 k가 되도록하는 경우의 수를 출력하는 문제다.

풀이

처음에 아예 접근을 잘못해서 시간을 많이 써버린 문제다..
DP는 점화식을 세우려는 노오력이 필요하다.

누적해서 계속 더해간다고 생각하면 된다.
예를 들어 5원을 가지고 6원을 만드는 것은
1원을 만드는 경우의 수를 기존 6원을 만드는 경우의 수에 더하는 것이다.

이것을 점화식을 세우면
현재 사용할 동전: i
만들고자 하는 수: x
dp[x] = dp[x]+ dp[x-i]

코드

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001], n, k, temp;
int main()
{
    cin >> n >> k;
    dp[0] = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        if (temp > 10000)
            continue;
        for (int j = temp; j <= k; j++)
        {
            dp[j] += dp[j - temp];
        }
    }
    cout << dp[k] << "\n";
}