동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다.
문제의 링크입니다.
https://www.acmicpc.net/problem/2293
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
주어진 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;
}
반응형
'Programming > BOJ' 카테고리의 다른 글
[C/C++] 백준 #2302 극장 좌석(동적 계획법) (0) | 2023.04.20 |
---|---|
[C/C++] 백준 #2294 동전 2(동적 계획법) (0) | 2023.04.20 |
[C/C++] 백준 #2290 LCD Test(구현) (0) | 2023.04.20 |
[C/C++] 백준 #2268 수들의 합 7(세그먼트 트리) (0) | 2023.04.19 |
[C/C++] 백준 #2261 가장 가까운 두 점(분할 정복) (0) | 2023.04.19 |
댓글