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

www.acmicpc.net/problem/2293

2293번: 동전 1

 

문제 예제

 

문제의 예제 1은 1, 2, 5의 가치를 가지는 동전으로 10원을 만들 수 있는 경우의 수를 구하는 문제이다. 

 

각 경우의 수를 따져 보았을 때 다음과 같은 표를 도출해 낼 수 있다. 

i	각 i가 나오는 경우	경우의 합
1	[1]	1
2	[1+1], [2]	2
3	[1+1+1], [2+1]	2
4	[1+1+1+1], [2+1+1], [2+2]	3
5	[1+1+1+1+1], [2+1+1+1], [2+2+1], [5]	4
6	[1+1+1+1+1+1], [2+1+1+1+1+1], [2+2+1+1], ...	5
7	...	6
8	...	7
9	...	8
10	...	10

위의 표만으로는 명확하게 이해할 수 없으니 정리를 하자면, 

 

처음에는 1만을 이용해서 각 i 의 가치를 만들 수 있는 경우의 수를 따진다. 그러면 다음과 같은 표를 도출해 낼 수 있다. 

i	첫번째 동전 1만을 사용하여 i가 나오는 경우	경우의 합
1	[1]	1
2	[1+1]	1
3	[1+1+1]	1
4	[1+1+1+1]	1
5	[1+1+1+1+1]	1
6	[1+1+1+1+1+1]	1
7	...	1
8	...	1
9	...	1
10	...	1

 

그 다음은 1과 2를 사용하여 i의 가치를 만들어낼 수 있는 경우의 수를 따진다. 그러면 다음과 같은 표를 도출해 낼 수 있다. 

앞의 1만 사용해서 가치를 만들어 내는 경우 점화식을 만들어내기 힘들었는데 이젠 조금씩 보이기 시작한다. 

1부터 각 칸을 업데이트 해나간다고 할때, 자신보다 두개 앞선 값을 자신에게 더해주는 것을 발견할 수 있다. 식으로 표현하면

d[i]=d[i]+d[i-(2)]로 된다. 여기까지 생각하고 다음으로 넘어가보쟈!

 

i	각 i가 나오는 경우	경우의 합
1	[1]	1
2	[1+1], [2]	2
3	[1+1+1], [2+1]	2
4	[1+1+1+1], [2+1+1], [2+2]	3
5	[1+1+1+1+1], [2+1+1+1], [2+2+1]	3
6	[1+1+1+1+1+1], [2+1+1+1+1+1], [2+2+1+1], ...	4
7	...	4
8	...	5
9	...	5
10	...	6

 

다음은 1,2,5를 이용하여 각 i 를 만드는 경우의 수를 따진다. 그러면 다음과 같은 표를 도출해 낼 수 있다. 

그러면 앞서 1,2만을 사용하여 i를 만들었던 경우의 수 표와 비교 하였을 때, 5를 이용해 수를 만들 수 있게 된 경우부터 수가 update되는 것을 확인할 수 있다. 그렇게 따졌을 때 단지 d[i]=d[i]+d[i-(2)]로는 문제를 풀 수없었다. 

잘 살펴보면 d[i]=d[i]+d[i-(5)]의 규칙이 있는 것을 확인할 수 있다. 

 

i	각 i가 나오는 경우	경우의 합
1	[1]	1
2	[1+1], [2]	2
3	[1+1+1], [2+1]	2
4	[1+1+1+1], [2+1+1], [2+2]	3
5	[1+1+1+1+1], [2+1+1+1], [2+2+1], [5]	4
6	[1+1+1+1+1+1], [2+1+1+1+1+1], [2+2+1+1], [2+2+2], [5+1]	5
7	...	6
8	...	7
9	...	8
10	...	10

 

그렇게 update 되는 시점을 생각하여 다음과 같은 코드를 도출한다. 그러면 각 1,2,5를 사용하여 10을 만들어내는 경우의 수가 d[10]에 누적되어 있을 것이다. 

 if (j >= input[i]) 
         d[j] += d[j - input[i]];

 

다음은 최종 코드이다! 👾

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int d[10001] = {
        0,
    };
    int n, k;
    vector<int> input;

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int in;
        cin >> in;
        input.push_back(in);
    }


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

    cout << d[k] << "\n";
    
    return 0;
}