BOJ 2293

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ2293 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        /**
         *   1 2 3 4 5 6 7 8 9 10
         * 1 1 1 1 1 1 1 1 1 1 1
         * 2 0 1 1 2 2 3 3 4 4 5
         * 5 0 0 0 0 1 1 2 2 3 4
         * t 1 2 2 3 4 5 5 7 8 10
         *
         */

        // coin의 정보
        int[] coin = new int[101];
        int[] dp = new int[10001];

        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);

        for (int i = 1; i <= n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        // dp[j-coin[i]] 가 0일 경우 대비해 1 넣어줌
        dp[0] = 1;

        // 코인의 종류만큼 돌림
        for (int i = 1; i <= n; i++) {
            // k만큼 돌림
            for (int j = coin[i]; j <= k; j++) {
                // dp[j] = dp[j] (기존) + dp[j - i번째 코인]
                dp[j] += dp[j - coin[i]];
            }
        }

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


    }
}

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

2293번: 동전 1