[JAVA] 백준 알고리즘 2293 : 동전 1 (DP)

 

 

문제

 

 

 

 

소스

 

import java.util.Scanner;

public class Main {

    static int N,K;
    static int coin[], dp[];

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        coin = new int[N+1];
        dp = new int[K+1];

        for (int i=1; i<=N; i++) {
            coin[i] = sc.nextInt();
        }

        dp[0] = 1;
        for (int i=1; i<=N; i++) {
            for (int j=0; j<=K; j++) {
            	if(j-coin[i] >= 0) {
                	dp[j] = dp[j] + dp[j - coin[i]];
                }
            }
        }

        System.out.println(dp[K]);
    }
}

 

 

출처

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