[Java] 백준 2293 동전 1

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

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

풀이

예를 들어,

입력이 아래와 같다고 하면

3 10
1
2
5

동전 종류: 1, 2, 5

목표 금액: 10

🔹 DP 테이블 갱신 과정

동전 사용	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
초기값	1	0	0	0	0	0	0	0	0	0	0
1원 사용	1	1	1	1	1	1	1	1	1	1	1
2원 사용	1	1	2	2	3	3	4	4	5	5	6
5원 사용	1	1	2	2	3	4	5	6	7	8	10

→ dp[10] = 10 이므로 10원을 만드는 방법은 총 10가지

• dp[i] = i원을 만드는 방법의 수
• 초기값: dp[0] = 1 (아무 동전도 사용하지 않는 경우)
• 점화식:
  dp[j]+=dp[j−coin]
  
• 동전을 하나씩 고려하면서 업데이트 (중복 방지를 위해 각 동전별로 한 번씩만 반복)

정답코드

import java.io.*;
import java.util.*;

public class Main {
    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());
        }

        // 1. dp 테이블
        int[] dp = new int[10001]; // n의 최댓값

        // 2. 초기값
        dp[0] = 1; // 0을 만드는 경우의 수는 1가지

        // 3. 점화식
        for (int i = 1; i <= n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        System.out.println(dp[k]);
    }
}