백준 2293번 동전1 Java(자바) 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G5_2293_동전1 {
	
	static BufferedReader br;
	static StringTokenizer st;
	static int n, k;
	static int[] coins, dp;

	public static void main(String[] args) throws IOException {
		
		// System.setIn(new FileInputStream("./input.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 동전 종류
		k = Integer.parseInt(st.nextToken()); // 동전 합
		
		coins = new int[n + 1];
		dp = new int[k + 1];
		for(int i = 1; i <= n; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		
		dp[0] = 1;
		for(int i = 1; i <= n; i++) {
			// coins[i] 동전으로 만들 수 있는 경우의 수를 dp에 순차적으로 더한다
			// ex) 1원 짜리 경우의 수 dp에 다 더하고 -> 2원 짜리 경우의 수 dp에 다 더하고..
			for(int j = coins[i]; j <= k; j++) {
				dp[j] = dp[j] + dp[j - coins[i]]; 
			}
		}
		
		System.out.println(dp[k]);

	}

}