[C/C++] 백준 #2624 동전 바꿔주기(동적계획법)

동전 바꿔주기 문제는 여러 종류의 동전을 가지고 원하는 액수의 금액을 맞추어주는 경우의 수 문제입니다.

실생활에서는 크게 도움이 되지 않겠지만, 동적계획법을 이용한 알고리즘 문제로는 매우 유명합니다.

 

coin changes

 

동적계획법을 사용할 때에는 보통 다차원 배열을 이용하게 되는데, 다차원 배열 대신에 맵(map) 또는 딕셔너리(dictionary) 자료를 이용해서도 문제를 풀 수 있습니다.  중간에 생기는 상태값의 갯수에 비해서 키(key)의 범위가 매우 큰 경우에는 다차원 배열보다는 맵 자료형을 사용하는 것이 좋습니다.  이것은 대략적인 감에 의존할 수밖에 없습니다.  다차원 배열이나 정렬되지 않은 맵(unordered map) 모두 $O(1)$ 검색 알고리즘이지만, 정렬되지 않은 맵을 처리하기 위해서는 오버로드가 그만큼 크니까, 키의 범위가 크지 않다면 다차원 배열이 좋습니다.

 

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

 

이번 문제는 동전 액수의 크기가 10,000 이하로 크지 않아서 다차원 배열을 이용하는 것이 훨씬 유리하다고 볼 수 있습니다.  저는 정렬되지 않은 맵을 이용해서 문제를 풀었지만.

 

동전의 종류에 따라서 기존 키값을 찾아서 계산해주어야 하기 때문에 한쌍의 맵 자료형을 이용했습니다.  참고로 다차원 배열인 경우에는 동전을 더하는 경우밖에 없으므로 하나의 배열로 문제를 풀 수 있는 장점이 있습니다.

 

이러한 문제를 풀 때, 또한 주의해야 하는 것이 0이란 금액을 맞추기 위한 경우의 수입니다.  0이란 금액을 맞추기 위한 경우의 수를 0이라고 잘못 생각할 수 있지만, 0을 만들 수 있는 경우의 수는 공집합($\varphi$) 한가지가 있으므로 경우의 수는 1입니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2624
//        - by Aubrey Choi
//        - created at 2019-08-06
//------------------------------------------------
#include <stdio.h>
#include <unordered_map>

int main()
{
    int t, k;
    std::unordered_map<int, unsigned> map[2];
    map[0][0]=1; map[1][0]=1;
    scanf("%d%d", &t, &k);
    while(k--)
    {
        int c=k&1, n, p;
        scanf("%d%d", &p, &n);
        map[c].clear();
        for(const auto &it : map[c^1])
        {
            for(int i=0;i<=n;i++)
            {
                if(it.first+p*i > t) break;
                map[c][it.first+p*i] += it.second;
            }
        }
    }
    printf("%u\n", map[0][t]);
    return 0;
}