[BOJ 2293] 동전 1 - java

BOJ 2293번: 동전 1

dp[n][k] ⇒ n번째 코인까지만 사용하여, K원을 만드는 경우의 수!

for (int n = 1; n <= N; n++) {
    for (int k = 1; k <= K; k++) {
        if (k == coins[n]) dp[n][k] = dp[n - 1][k] + 1;
        else if (coins[n] > k) dp[n][k] = dp[n - 1][k];
        else dp[n][k] = dp[n - 1][k] + dp[n][k - coins[n]];
    }
}

1. coins[n] == k인 경우, 👉 coins[n]을 처음으로 포함시킬 수 있게 됨!

   dp[n][k] = dp[n - 1][k] + 1

   

2. coins[n] > k인 경우, 👉 coins[n]을 포함시키지 못함. 따라서 이전 dp값 가져오기만 함!

   dp[n][k] = dp[n - 1][k]

   

3. coins[n] < k인 경우, 👉 coins[n]을 포함시키지 않은 경우 dp[n - 1][k] + coins[n]을 포함시키는 경우 dp[n][k - coins[n]]

   dp[n - 1][k] + dp[n][k - coins[n]]

   

전체 코드

package boj;

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

// 백준 2293번: 동전 1
public class BOJ_2293 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] coins = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[N + 1][K + 1];

        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= K; k++) {
                if (k == coins[n]) dp[n][k] = dp[n - 1][k] + 1;
                else if (coins[n] > k) dp[n][k] = dp[n - 1][k];
                else dp[n][k] = dp[n - 1][k] + dp[n][k - coins[n]];
            }
        }

        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= K; k++) {
                System.out.print(dp[n][k] + " ");
            }
            System.out.println();
        }

        System.out.println(dp[N][K]);
    }
}