백준 9084번, 동전(C, C++)
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
다이나믹 프로그래밍(DP)으로 문제를 해결하였습니다.
간단한 예시로 {1원, 2원, 3원} 3종류의 동전이 있습니다.
0원의 값을 만들기 위해서는 아무것도 사용하지 않는 경우 1가지가 있습니다.
1원의 값을 만들기 위해서는 1원 한 가지의 경우입니다.
2원의 값을 만드는 경우는 1+1, 2 2가지가 있습니다.
3원의 값을 만드는 경우는 1+1+1 , 1+2, 3이 있습니다.
위 그림을 자세히 살펴보면 1원, 2원, 3원 ,4원을 만드는데 1원이 무조건 들어갑니다.
기본적으로 1원으로 만드는 경우의 수 1가지가 무조건 들어간 다는 것을 알 수있죠.
그러면 기본적으로
dp[1] ~ dp[4] = 1이라는 경우의 수를 가질 것입니다.
2원이라는 동전을 사용하면, 1가지 경우의 수가 늘어 dp[2] = 2가 될 것이고,
dp[3] 또한 2가지의 경우의 수를 가질 것 입니다.
dp[4] 또한 1 + 1 + 2와 2 + 2 라는 경우의 수가 추가 되어 dp[4] = 3이 됩니다.
다시 돌아가 3원을 추가하여 1~4원을 만드는 경우를 살핍니다.
dp[1], dp[2]는 3원이 들어갈 수 없습니다.
dp[3]은 3원짜리로 만드는 경우의 수를 추가하여 3가지의 경우의 수를 이룹니다.
dp[4]는 1+3인 경우가 추가되어 4가지를 만들어집니다.
위 그림 순서처럼 흘러갑니다.
그림을 살펴보면,.
1원만 사용한 4원을 만드는 경우의 수 더하는 사이클이 돌고나면, 2원을 사용한 4원을 만드는 사이클이 돌고, 3원을 사용한 4원 사이클이 돌면서 끝이납니다.
아래는 다음을 코드로 구현한 것 입니다.
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int T;
int N;
int M;
int arr[21];
int dp[10001];
cin>>T;
while(T--){
memset(dp, 0, sizeof(dp));
cin>>N;
for(int i = 1; i <= N; i++){
cin>>arr[i];
}
cin>>M;
dp[0] = 1;
for(int i = 1; i <=N; i++){
for(int j = arr[i]; j <= M; j++){
dp[j] += dp[j - arr[i]];
}
}
cout<<dp[M]<<'\n';
}
return 0;
}