<링크>
https://www.acmicpc.net/problem/9084
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include<stdio.h> int coin[20]; int main() { int T; scanf("%d", &T); while (T--) { int N; scanf("%d", &N); for (int i = 0; i < N; ++i) scanf("%d", coin + i); int M; scanf("%d", &M); int dp[10001] = { 1, }; for (int i = 0; i < N; ++i) { for (int j = coin[i]; j <= M; ++j) dp[j] += dp[j - coin[i]]; } printf("%d\n", dp[M]); } } | cs |
<풀이>
가장 대표적인 다이나믹프로그래밍 유형 중의 하나이다.
동전을 하나씩 집어서 1원~M원까지 만들수있는 경우의수를 만들어간다.
시간은 M*N이 된다.
'알고리즘 풀이 > DP' 카테고리의 다른 글
백준 1005 ACM Craft (0) | 2018.08.06 |
---|---|
백준 9095 1,2,3 더하기 (0) | 2018.07.26 |
백준 14501 퇴사 :: 들짐승 (1) | 2018.07.22 |