acmicpc

[BAEKJOON] 2293. 동전1

코드와이 2021. 4. 24. 01:34

 

DP

문제링크

www.acmicpc.net/problem/2293

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

package acmicpc.Silver1;

import java.util.Scanner;

public class 동전1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] num = new int[n];
		int[] dp = new int[k+1];
		dp[0] = 1;
		
		for(int i = 0 ; i < n ; i++) {
			num[i] = sc.nextInt();
			for(int j = num[i] ; j <= k ; j++) {
				dp[j] += dp[j - num[i]];
			}
		}
		System.out.println(dp[k]);
	}
}