Search
Duplicate
🥑

동전 2

주차
13
문제번호
2294
언어
티어
실버
유형
DP
nj_Blog
nj_상태
완료
이해도
풀이
사람
이해도 2
13 more properties

Memo

Memory : 2016 KB

Time : 4 ms

Code

#include<bits/stdc++.h> int main() { int coin[100]; int dp[10001]; int n,k; scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&coin[i]); } for(int i=1;i<=k;i++) dp[i] = 10001; dp[0] = 0; for(int i=0;i<n;i++){ for(int j=1;j<=k;j++){ if (coin[i] > j) continue ; dp[j] = (dp[j] < dp[j - coin[i]] + 1) ? dp[j] : dp[j - coin[i]] + 1; } } if (dp[k] == 10001) dp[k] = -1; printf("%d",dp[k]); }
C++
복사