https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
[난이도] Gold5
[유형] DP
[풀이]
dp[i] : i원을 만들 수 있는 경우의 수.
#include <cstdio>
#include <cstring>
using namespace std;
int tc,N,M,a[20],dp[10001];
int main(){
scanf("%d",&tc);
while(tc--){
scanf("%d",&N);
memset(dp,0,sizeof(dp));
for(int i=0;i<N;i++) scanf("%d",&a[i]);
scanf("%d",&M);
dp[0]=1;
for(int i=0;i<N;i++)
for(int j=1;j<=M;j++)
if(j-a[i]>=0) dp[j]+=dp[j-a[i]];
printf("%d\n",dp[M]);
}
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/9084.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold5] 2666 : 벽장문의 이동 (C++) (0) | 2021.06.24 |
|---|---|
| [BOJ/백준][Gold5] 17141 : 연구소 2 (C++) (0) | 2021.06.24 |
| [BOJ/백준][Gold5] 20056 : 마법사 상어와 파이어볼 (C++) (0) | 2021.06.24 |
| [BOJ/백준][Gold5] 1188 : 음식 평론가 (C++) (0) | 2021.06.24 |
| [BOJ/백준][Gold5] 14719 : 빗물 (C++) (0) | 2021.06.24 |