[Algorithm] Baekjoon 9084번 : 동전

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

9084번: 동전

 
 
int t, n, m;
int coins[21] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        int dp[10001] = { 0 };
        dp[0] = 1;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> coins[i];
        }
 
        cin >> m;
 
        for (int i = 0; i < n; ++i)
        {
            int coin = coins[i];
 
            for (int j = coin; j <= m; ++j)
            {
                dp[j] += dp[j - coin];
            }
        }
 
        cout << dp[m] << endl;
    }
}

 

이 문제랑 똑같은 문제가 프로그래머스에 있었는데, 그때는 풀이를 봐도 잘 이해가 안갔었다.

지금은 얼추 이해가 간다.. 뭔가 명확하게 설명은 못하겠다만.

참고로 문제에서 동전단위는 오름차순으로 주어지는데, 내림차순이여도 상관없다.

 

주어진 동전들 중, 가장 작은동전을 기준으로 잡고 해당동전의 값부터 목표값(5라고 가정)까지 해당 동전을 '활용'해서

만들 수 있다면 dp값에 누적시킨다.

코드에 if문이 없는데 만들수있다'면' 이라고 말하는게 뭔소린가? 할 수 있다.

이것은 기준동전을 사용하고 남은 나머지값에 대한 경우의 수를 누적시키는 과정에서, 남은 나머지값에 대한 경우의 수가 0이라면, 즉 목표값 j를 만들지 못할 경우 0이 합산되기 때문에 '만들수없다'라고 표현할 수 있기 때문에, 만들수있다'면' 이라고 설명한 것이다.

 

동전 1,2,5가 있고 m이 5라고 가정해보자.

dp[0]에는 1을 넣어둔다. dp[n]의 의미는 주어진 동전들을 모두 활용해서 n을 만들 수 있는 경우의 수를 의미하는데, 0을 만들기위해서는 모든 동전을 이용 안하면 만들 수 있다. 그렇기 때문에 dp[0] = 1이다.

 

기준동전 1을잡고, j를 1부터 m까지 반복해서 dp[j] += dp[j-1] 을 수행할 것이다.

-1이기 때문에 바로 이전 dp값을 계속 누적시키게 될 것인데, dp[0]이 1이기 때문에 결국 dp[m]까지 전부 1을 더하게 된다.

1원짜리 동전으로는 뭐든지 만들 수 있기에 당연하다.

 

기준동전 2를 잡아보자. 마찬가지로 j를 2부터 m까지 반복해서 dp[j] += dp[j-2]를 수행할 것이다.

j를 기준동전부터 시작해야하는걸 잊지말자. 당연하게도, 기준동전으로 만들 수 있는 최솟값은 자기 자신이기 때문이다.

2원짜리로 1원짜리는 못만드니까

 

dp[2] += dp[2-2] => dp[2] += dp[0] => dp[0]에는 1이들어있으니 자연스럽게 dp[2]에는 1이 누적된다.

즉, 2원짜리 동전 한개를 사용했을 때, 나머지값인 0을 만들기 위한 모든경우의수 1가지가 누적된 것이다.

 

그러면 j가 3이라면? 즉 목표값이 3이라면 dp[3] += dp[3-2 == 1] 이 수행될것이다.

이 말은 목표값 3을 만들기위해 2원짜리 동전을 사용한 다음, 1원짜리를 만들기위한 모든경우의수를 누적시킨다는 것이다. 우리는 1원짜리 동전이 있었기 때문에 dp[1]에는 1의 값이 누적되있으니, dp[3]에는 1을 누적시킬 것이다.

 

이렇게 bottom-up 방식으로 모든 경우의 수를 누적시키면서 완성해간다.

여기까지 했을 경우, 이런식으로 헷갈릴 수 있다.

'같은 동전을 여러개 사용할 수도 있는데 이게 맞나?' 라고.

 

하지만 동전단위가 낮은것부터 시작해서 목표m값까지의 모든 값들에 전부 누적시켰기 때문에, 이미 dp[j-coin]에는 이전에 기준동전을 사용했던 경우가 전부 포함되어있다.