[C/C++] 백준 #2293 동전 1(동적 계획법)

동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다.

 

coins

 

문제의 링크입니다.

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

2293번: 동전 1

주어진 K원을 만들기 위해서는 동전의 종류를 먼저 조절해야 합니다.  서로 다른 동전의 종류가 n개가 있다면, 우리는 동적 계획법의 변수 \(d_{n, k}\)를 정의하도록 합니다.  n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다.

 

이렇게 하면 다음과 갈은 식을 도출할 수 있습니다.  \(c_i\)는 i번째 동전의 금액입니다.

 

\[ d_{0, 0} = 1 \]

\[ d_{i, j} = \sum_{t = 1}^{\lfloor j/c_i \rfloor} d_{i-1, j-c_i \cdot t} \]

 

이 식을 적용해서 소스를 작성하면 다음과 같습니다.

//------------------------------------------------
//    baekjoon #2293
//        - by Edan
//        - created at 2019-08-07
//------------------------------------------------
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
bool cmp(int a, int b) { return a>b; }

int main()
{
    int n, k, v[100], c = 0;
    std::unordered_map<int, unsigned> map[2];
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++) scanf("%d",v+i);
    std::sort(v, v+n, cmp);
    map[1][0]=1;
    for(int i=0;i<n-1;i++)
    {
        if(v[i]>k) continue;
        map[c].clear();
        for(const auto &it : map[c^1])
            for(unsigned s=it.first;s<=k;s+=v[i]) map[c][s]+=it.second;
        c^=1;
    }
    unsigned ans=0;
    for(const auto &it : map[c^1]) if((k-it.first)%v[n-1]==0) ans += it.second;
    printf("%u\n", ans);
    return 0;
}