백준 동전 1 [c++]

동전 1 골드5

문제

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

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

문제 풀이

• 1원을 만드는 경우의 수 = 1가지
• 2원을 만드는 경우의 수 = 2가지(1원짜리로만 2원을 만드는 방법 1가지 + 2원짜리로 2원을 만드는 방법 1가지)
• 3원을 만드는 경우의 수 = 3가지(1원짜리로만 3원을 만드는 방법 1가지 + (1원+2원)로 3원을 만드는 방법 1가지 + 3원짜리로 3원을 만드는 방법 1가지)
• x원인 동전을 가지고 있다면, Y원을 만들고 싶다면, DP[Y] = DP[Y] + DP[Y-X]
• x원 짜리로 어떤 금액을 만들려면 어떤 금액은 x보다 크거나 같아야 한다.

코드

#include <iostream>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    int coin[n];
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }
    int dp[k + 1];
    for(int i = 0; i <= k; i++)
    {
        dp[i] = 0;
    }
    dp[0] = 1;
    
    for(int i = 0; i < n; i++)
    {
        for(int y = coin[i]; y <= k; y++)
        {
            dp[y] += dp[y - coin[i]];
        }
    }
    cout << dp[k] << endl;

    return 0;
}

총평

• 단순히 합이 k인 수로 dp식이 나오지 않는 문제.
• 수단인 동전의 값으로 생각해야 함.

• ps
• dp