PS
[백준] 9084번 동전 C++
Eastplanet
2022. 6. 30. 11:41
문제 출처: https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
coin(현재 사용할 동전 idx, 만들어야 하는 값) 함수를 구현하여 탑다운 방식으로 풀었다.
coin(idx , value) = coin(idx+1, value) + coin(idx+1, value - 1*arr[idx]) + coin(idx+1 , value - 2*arr[idx]) + ...
의 점화식을 세울 수 있다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>
using namespace std;
int N, M;
int arr[21];
int dp[21][10001];
int coin(int idx, int nowVal) {
if (idx == N) {
if (nowVal == 0)return 1;
else return 0;
}
if (dp[idx][nowVal] != -1)return dp[idx][nowVal];
int val = 0;
for (int i = 0; i < 10001; i++) {
if (nowVal - arr[idx] * i >= 0)val += coin(idx + 1, nowVal - arr[idx] * i);
else break;
}
return dp[idx][nowVal] = val;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T; cin >> T;
while (T--) {
fill(&dp[0][0], &dp[20][10001], -1);
cin >> N;
for (int i = 0; i < N; i++)cin >> arr[i];
cin >> M;
cout << coin(0, M)<<'\n';
}
}