[JAVA] 백준 2293번_동전 1

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

2293번: 동전 1

- 재귀형식 완전 탐색으로 실행 -> 실패

- 메모리 제한 때문에 dp 사용해서 풀어야 함

- dp[k] = dp[k - coin] 까지밖에 생각 못함..... 해당 값을 구성하는 경우의 수도 생각해야 함 

   => dp[k] = dp[k: 이전 k 경우의 수] + dp[k - coin]

- coin 값 종류별로 dp[k] 후보군 구한 후 max 할당

조합의 중복을 막기 위해서, 사용하는 동전 종류를 점진적으로 늘려가기

1. 첫 번째 동전만 사용하는 경우 -> idx % coin == 0인 경우만 1 할당
2. 두 번째 동전 사용 -> 첫 번째 동전만 사용한 값 기반으로 dp[coin] + dp[k-coin] 사용
   • dp[idx]에서 idx >= k인 경우만 고려 (나머지는 0)

   EX) 동전 값 2 => dp[2] = dp[0] + dp[2] = 2, dp[3] += dp[1] (=2)

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5	5	6
5	0	0	0	0	4	5	6	7	8	10

---

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

public class Main {
    static int n, k, value;
    static List<Integer> coin;
    static int[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); k = sc.nextInt();
        coin = new ArrayList<>();
        while (n-- > 0) {
            value = sc.nextInt();
            if(value <= k) coin.add(value);
        }
        dp = new int[k + 1];
        dp[0] = 1;
        for (int i = 0; i < coin.size(); i++) {
            value = coin.get(i);
            for (int j = coin.get(i); j <= k; j++) {
                dp[j] += dp[j - value];
            }
        }
        System.out.println(dp[k]);
    }
}