[BOJ] 동전1 C++ 풀이

문제

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

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

입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

접근방법

예제에서는 1, 2, 5원짜리 동전이 주어지고 이를 각각 이용하여 10원을 만드는 경우를 얘기하고 있지만 여기서는 간단하게 1, 2, 3원짜리 동전으로 5원을 만든다고 가정해 보겠다.

먼저 5원은 1원짜리 5개로 만들수 있다. 이 과정에서 1원짜리로 4,3,2 원을 만드는 것도 가능하다는 것을 알 수 있다.

그렇다면 2원을 기준으로 5원을 만들수 있는 경우는 어떻게 될까

2원이 5원이 되기 위해서는 3원이 필요하다는 것을 알 수 있다. 이 때, 앞에서 구했던 3원을 만들 수 있는 경우의 수를 미리 저장해 놓고 사용한다면 빠르게 구할 수 있다. $($1원 3개, 3원 1개, 2원 1개 + 1원 1개)

메모이제이션을 사용하여 문제를 접근해 보았다.

dp[i] = x; 에서 i는 동전의 가치이고 x는 주어진 동전들의 조합으로 i가치를 만들 수 있는 경우의 수이다.

즉, 위의 형식은 n개 동전들로 i가치를 만들때 가능한 경우의 수를 의미한다.

구현

#include<iostream>
#include<vector>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k;
    int dp[100001];
    cin>>n>>k;

    vector<int> coin(n+1, 0);

    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;
}