[백준/C,C++] 2293번: 동전 1

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

2293번: 동전 1

풀이

생각보다 어려운 문제였습니다.

 

1, 2, 5원을 1번 이상 사용해 만들 수 있는 1~10원의 경우의 수는 아래 표와 같습니다.

 

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
누적	1	1	1	1	1	1	1	1	1	1	1
2	0	0	1	1	2	2	3	3	4	4	5
누적	1	1	2	2	3	3	4	4	5	5	6
5	0	0	0	0	0	1	1	2	2	3	4
누적	1	1	2	2	3	4	5	6	7	8	10

 

5원을 사용해 8원을 만드는 방법을 생각해봅시다.

 

5원을 1번 사용한다면 나머지 3원은 1, 2원으로 구성돼 있을 것입니다.

 

1, 2원으로 3원을 만드는 방법은 1 + 1 + 1 / 1 + 2로 총 2가지입니다.

 

그렇기 때문에 5원을 사용해 8원을 만드는 경우의 수는

 

1, 2원을 사용해 3원을 만드는 경우의 수와 같다고 볼 수 있습니다.

 

 

10원의 경우 5원이 무조건 1번 이상 포함된 경우의 수를 살펴봅시다.

 

1, 2, 5원을 사용해 나머지 5원을 만드는 방법은 총 4가지입니다.

 

1 + 1 + 1+ 1 + 1 / 1 + 1 + 1 + 2 / 1 + 2 + 2 / 5 이렇게 4가지가 있죠.

 

그래서 5원을 꼭 사용해 10원을 만드는 방법은 마찬가지, 4가지로 동일합니다.

 

왜냐하면 각 경우의 수에 5원을 얹어주면 되는 것이죠.

 

1 + 1 + 1 + 1 + 1 + 5 / 1 + 1 + 1 + 2 + 5 / 1 + 2 + 2 + 5 / 5 + 5

 

 

마지막으로 한 번 더 생각해봅시다.

 

2원을 1번 이상 꼭 사용해 7원을 만든다고 생각해봅시다.

 

이는 1, 2원을 사용해 5원을 만드는 경우의 수와 같습니다.

 

1 + 1 + 1 + 1 + 1 / 1 + 1 + 1 + 2 / 1 + 2 + 2 총 3가지의 경우가 있는데,

 

여기에 2원을 얹어주면 7원이 됩니다.

 

#include <iostream>

using namespace std;

const int MAX = 10001;

int cache[MAX];

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

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

    cout << cache[k];

    return 0;
}

반례

Input

5 1000
1
2
5
10
25

Output

18140751