본문 바로가기
Algorithm/DP(동적 계획법)

[백준][9084번][DP] 동전

by 우툴 2016. 10. 5.
728x90

동전


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
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
int value[10001]={0,};
 
int main() {
    int testcase;
    scanf("%d"&testcase);
 
    while(testcase--){
 
        int coinNum;
        int coin[21]={0,};
        for(int i=0;i<=10000;i++)
            value[i]=0;
            
        int lastNum;
        scanf("%d",&coinNum);
 
        for(int i=0;i<coinNum;i++){
            scanf("%d",&coin[i]);
        }
        scanf("%d",&lastNum);
 
        for(int i=0;i<coinNum;i++){
            value[coin[i]]++;
 
            for(int j=coin[i]+1;j<=lastNum;j++){
                value[j]= value[j] + value[j-coin[i]];
 
            }
 
        }
        printf("%d\n", value[lastNum]);
    }
 
    return 0;
}
cs


<문제 푼 요령>


 1. 이 문제는 동전이 오름차순으로 입력받는것이 큰 힌트이다. 


 2. 처음 현재의 코인 단독으로 나오는 가짓수인 value[nowCoin]++ 을 올려야 한다.

 

 3. 점화식은 value[i] = value[i] + value[i-nowCoin] 이렇게 되는데 저 점화식을 설명하자면 이전의 코인의 조합으로 만들어지는 경우의 수에 현재의 코인의 개수를 한개 늘렸을때의 가지수를 추가한 것이다. 


예를 들면 

 200원의 값을 예를 들고 현재의 코인이 100원이면 이전의 코인으로 만들어지는 경우의 수는 value[200] 인데 100원을 만드는 경우의 수에 100원을 추가하는 경우가 있기 때문에 이 경우의 수는 value[200-100(nowCoin)] 이된다. 즉 value[200] = value[200] + value[200-100(nowCoin)] 이 되는것이다.


 4. 중복이 발생하지 않을까 고민했는데 코인을 오름차순으로 입력을 받기 때문에 중복은 발생하지 않는다.



728x90

댓글