<링크>

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

+ Recent posts