https://www.acmicpc.net/problem/9084
9084호: 코인
한국 화폐 단위로는 1원, 5원, 10원, 50원, 100원, 500원이 있는데 특히 동전이 있습니다.
이 동전은 정수 금액을 만들 수 있으며 그렇게 하는 데는 여러 가지 방법이 있을 수 있습니다.
예를 들어 30원을 벌려면
![[백준, BOJ 10971] 외판원](https://in.eternals.kr/wp-content/plugins/contextual-related-posts/default.png "[백준, BOJ 10971] 외판원")
www.acmicpc.net
DP문제입니다.
dp 문제이기 때문에 테이블 세팅을 잘 해줘야 합니다.
d(a) = b: 원을 만드는 방법의 수는 b로 정의됩니다.
먼저 3개의 원을 만들어야 하고 1, 2, 3개의 원이 있다고 가정해 보겠습니다.
여기서 포인트는 “마지막에 코인을 사용하여 금액을 완성하는 과정”입니다.
1) 마지막에 1원을 사용하여 금액을 완성하고,
1원이 채워지고, 2원이 채워지고, 3원이 채워지는 경우가 있다.
1원을 1원으로 채우려면 0원이 있어야 하고,
2원을 1원으로 채우려면 1원이 필요합니다.
3을 1로 채우려면 2가 필요합니다.
2) 마지막에 2원을 사용하여 금액 완성하기
1만원도 채울 수 없습니다.
2원에서 채울 수 있기 때문에
2원으로 2원을 채우려면 0원이 있어야 하고,
2만원이 있고 3만원을 채우고 싶다면 1만원이 필요하다.
3) 마지막에 3원을 사용하여 금액 완성하기
1.2만원도 못 채운다.
3원에서 채울 수 있기 때문에
3원이 있고 3원을 채우려면 0원이 있어야 합니다.
따라서!
1원에서 3원으로(문장 바깥쪽)
1원으로 벌 수 있는 금액은 자기 돈에서 3원까지 다양하다.
(inner-for 문)
또한 d(0)의 값은 1입니다.
동전을 사용하지 않으면 0원을 만드는 방법은 하나뿐이기 때문이다.
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int v(10005); //동전금액
int d(10005); //d(a)=b : a원을 만들 수 있는 방법의 수가 b개
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tc; cin>>tc;
while(tc--){
fill(d, d+10005, 0);
cin>>n;
for(int i=1; i<=n; i++) cin>>v(i);
cin>>m;
d(0)=1;
for(int i=1; i<=n; i++){
for(int j=v(i); j<=m; j++){
d(j) = d(j) + d(j-v(i));
}
}
cout<<d(m)<<'\n';
}
}d(j) = d(j) +d(jv(i)); jv(i)에 v(i) 코인을 추가하는 것입니다.
원 j는 원 jv(i)에 v(i)를 더함으로써 얻어진다.
위의 예를 사용하면 3원은 3-1원에 1원을 더한 것입니다.
그래서 3원을 1원으로 채우기 위해서는 이미 2원을 가지고 있어야 하고, 2원을 가질 수 있는 경우의 수는 d(2)이다.
따라서 j의 양에 v(i)를 사용한 후 남은 양(=v(i)을 뺀 후)은 jv(i)이며, 이는 jv(i), d(jv(i)를 만드는 방법의 수입니다.
)) d(j)까지.
이 블로그는 문제를 이해하는 데 정말 많은 도움이 되었습니다!
( 백준 9084 ) 코인(C++)
백준의 동전(9084) 문제입니다.
아) = 비
yabmoons.tistory.com