백준 9084 동전

<링크>

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]);     } } Colored by Color Scripter

cs

<풀이>

가장 대표적인 다이나믹프로그래밍 유형 중의 하나이다. 

동전을 하나씩 집어서 1원~M원까지 만들수있는 경우의수를 만들어간다.

시간은 M*N이 된다.