백준

백준 2293 동전 1(Java)

Park DJ 2023. 2. 27. 00:35

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

 

2293번: 동전 1

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

www.acmicpc.net

 

Java 코드

 

import java.util.Scanner;
import java.util.ArrayList;

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

    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] arr = new int[n + 1];
    int[] dp = new int[k + 1];
    dp[0] = 1;
    for(int i = 1; i <= n; i++) arr[i] = sc.nextInt();

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

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