[2293] 동전 1

https://www.acmicpc.net/problem/2293

n개의 종류 동전을 주고!

k원을 만들 수 있는 경우의 수를 구하는 문제입니다.

종류가 1, 2, 5이고..

10원을 만든다고 가정하면!

1원 = 1(1가지)

2원 = 1 + 1

        2

3원 = 1 + 1 + 1

   2 + 1

4원 = 1 + 1 + 1 + 1,

        1 + 1 + 2

        2 + 2

5원 = 1 + 1 + 1 + 1 + 1

        1 + 1 + 1 + 2

         2 + 2 + 1

         5

......

이렇게 갈 것입니다.

그렇다면 점화식을 어떻게 세워야할까요???

5원을 구한다고 생각하면

4원에서 + 1을 한 경우(1가지)

3원에서 + 2을 한 경우(2가지)

0원에서 + 5를 한 경우(1가지)

이렇게 총 4가지입니다.

해결 방법은..

1원에 대해서 먼저 dp를 채워줍니다.

그렇다면 k원까지 dp가 각각 1원으로 채워질 것입니다.

그리고 2원에 대해서 또 채워줍니다.

dp[2]의 값은 1에서 2가되겠지요(2가 추가되었으므로)

3원도 마찬가지로 1에서 2가되겠지요(1 + 2가 추가됨)

4원은 3이 될것입니다. 이유는(3 + 1과 2 + 2가 추가됨)

표로 그리면서 풀면 편할 것입니다..

이것을 점화식으로 세우면 아래의 코드와 같습니다.

coin[i]에 대해서 k원까지 돌고..

그 다음 코인에 대해서 k원까지 돌고...

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

아래의 코드는 전체 코드입니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
int coin[MAX_SIZE];
int dp[10001];
 
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
 
    for(int i = 0; i < n; i++) scanf("%d", coin + i);
 
    dp[0] = 1;
 
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            if(j - coin[i] >= 0) dp[j] += dp[j - coin[i]];
        }
    }
    printf("%d\n", dp[k]);
    
    return 0;
}