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

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

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

 

coin changes

 

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

 

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

 

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

 

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

 

이러한 문제를 풀 때, 또한 주의해야 하는 것이 0이란 금액을 맞추기 위한 경우의 수입니다.  0이란 금액을 맞추기 위한 경우의 수를 0이라고 잘못 생각할 수 있지만, 0을 만들 수 있는 경우의 수는 공집합(\(\phi\)) 한가지가 있으므로 경우의 수는 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;
}