백준 2293(동전 1) c++

문제

2293번: 동전 1

n개의 동전이 주어지면 동전의 조합을 이용해 k원이 되는 경우의 수를 구하는 것입니다.

동전은 무한대로 쓸 수 있습니다.

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

예를 들어 n = 3이고 동전의 가치가 각각 1, 2, 5이고 k = 10이면 동전의 조합을 통해 10이되는 경우의 수는

10입니다.

 

처음에 봤을 떄 knapsack 문제와 비슷한 느낌을 받아 이차원 배열을 만들고 생각해봤습니다.

먼저 1원으로 1 ~ 10원을 만드는 경우의 수입니다.

다음 으로 1원과 2원으로 1 ~ 10원을 만드는 경우의 수입니다.

여기서 규칙성을 찾아 볼 수 있는데, 일단 현재 선택한 동전이 2이므로 2 미만의 동전은 절대 만들 수 없습니다.

따라서 현재 선택한 동전의 미만의 동전은 이전의 dp값으로 설정합니다. 

빨간색 부분과 파란색 부분을 잘 살펴보면

dp[3] = 이전dp[3] + 현재dp[3 - 2]

dp[4] = 이전dp[4] + 현재dp[4 - 2] 

라는 규칙성이 나옵니다.

이제 1, 2, 5원으로 1~10원을 만드는 경우의 수를 살펴보면 아래와 같습니다.

마찬가지로 5미만의 동전은 절대 만들 수 없기 때문에 이전 dp[1~4]는 그대로 사용됩니다.

따라서 규칙을 종합해봐서 점화식을 내면 다음과 같습니다.

 for (int i = 1; i <= n; i++)
    {
    for (int j = coin[i]; j <= k; j++)
    {
         dp[j] += dp[j - coin[i]];
    }
}

마지막으로 dp[0] = 1입니다 왜냐 하면 모든 동전을 선택하지 않으면 0이 되기 때문입니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
int n, k;
int coin[101];
int dp[10101];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> coin[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = coin[i]; j <= k; j++)
        {
            dp[j] += dp[j - coin[i]];
        }
    }

    cout << dp[k];

    return 0;
}