[백준] 동전1

참고 : www.acmicpc.net/problem/2293

 

 - dp 문제

 - 점화식이 그리기 어려워 다른 분 답을 참고함

 - dp[i] : i까지 도달하는 경우의 수 (dp[i] = dp[i - coin[j] ])

 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] coin = new int[n+1];
        int[] dp = new int[10001];
        dp[0] = 1; // 무조건 1가지 방법은 있음.
        for(int i=1; i<=n; i++) {
            coin[i] = sc.nextInt();
            for(int j=coin[i]; j<=k; j++) {
                dp[j] += dp[j - coin[i]];
            }
        }

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