[백준 2293] 동전 1 -JAVA //le_effort//

사용 알고리즘 : DP

 

동전 시리즈의 문제이다

 

아래의 코드만 이해하면 된다.

for(int i=0; i<n; i++) {
            for(int j=coin[i]; j<=k; j++) {
                dp[j] += dp[j-coin[i]];
            }
        }

 

동전 알고리즘은 개인적으로 마이구미님의 설명글이 제일 깔끔 한 것 같다.

https://mygumi.tistory.com/129

동전 교환 관련 문제 접근 :: 마이구미

 

 

전체 코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,k;
    static int coin[];
    static int dp[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        coin = new int[n];
        dp = new int[k+1];
        for(int i=0; i<n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        dp[0]=1;
        
        for(int i=0; i<n; i++) {
            for(int j=coin[i]; j<=k; j++) {
                dp[j] += dp[j-coin[i]];
            }
        }
        for(int i=1; i<=k; i++) {
            System.out.println(dp[i]);
        }
        System.out.println(dp[k]);
    }
}