[백준 2293번] 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

---

풀이

DP(동적계획) 은 점화식이 중요하다. 그렇기 때문에 해당 문제의 규칙을 찾아서 점화식을 세우고 그걸 기반으로 코드를 짜야한다. 예를 들어보자

예시

최대 3종류 사용가능하며 10을 만들어야한다. 그렇다면 먼저 1원을 사용해서 만들수 있는 가치를 살펴보자

i) 1원으로 조합 가능한 경우

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

 

ii) 1,2원으로 조합 가능한 경우

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

 

iii) 1,2,5원으로 조합 가능한 경우

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	6	6	7	8	10

마지막으로 이 세가지 경우를 합쳐보겠다

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
1	2	2	3	3	4	4	5	5	6
1	2	2	3	4	6	6	7	8	10

이걸보면 점화식을 알 수있다. 만약 n종류로 k번째 가치를 만드는 경우는

dp[k]=dp[k](이전 값)+dp[k-coin[n]] 이다. 만약 3가지 종류를 만드는 경우에서, 10번째 값을 원한다면, 

dp[10]=6+dp[10-5]=6+4=10 인것이다. 

---

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    
    
    

    public static void main(String args[]) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        int [] coin= new int[n];
        int [] dp=new int[k+1]; //0인경우도 포함
        for(int i =0;i<n; i++) {
        	coin[i]=Integer.parseInt(br.readLine());
        }
        for(int i=0; i<=k;i++) {
        	if(i%coin[0]==0)
        		dp[i]++;
        }
        for(int i=1;i<n;i++) {
        	for(int j=1; j<=k;j++) {
        		if(coin[i]<=j) {
        			//점화식 
        			dp[j]=dp[j]+dp[j-coin[i]];
        			
        		}
        		
        	}
        }
        System.out.print(dp[k]);
    }

   
}