2293. 동전 1

2293. 동전 1

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

---

동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS)

구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.

이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다.

예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다.

유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ83Q3QGc

import java.util.Scanner;

public class Main {

    public int problem2293(int[] coins, int k) {
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; ++i) {
            for (int j = coins[i]; j < k + 1; ++j) {
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
        return dp[k];
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] coins = new int[n];
        for (int i = 0; i < n; ++i) {
            coins[i] = sc.nextInt();
        }

        System.out.println(main.problem2293(coins, k));
    }
}