백준 2293번 자바 : 동전1

다이나믹 프로그래밍

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int n,k;
    static int[] coin;
    static int[] dp = new int[10001];
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        coin = new int[n];
        for(int i=0; i<n; i++) {
            coin[i] = sc.nextInt();
        }

        // dp[i] => 동전을 사용해서 i원을 만드는 경우의 수
        dp[0] = 1;
        for(int i=0; i<n; i++) {
            for(int j=coin[i]; j<=k; j++) {
                dp[j] = dp[j] + dp[j-coin[i]];
            }
        }

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


}