BOJ_2293 : 동전 1

👉 문제링크

2293번: 동전 1

---

---

🔸 문제 분석 🔸

• n가지 동전으로 k원을 만드는 경우의 수를 출력한다.
• 동전을 무한으로 쓸 수 있으면 전형적인 DP문제로, dp[i] 는 i원을 만들 수 있는 경우의 수이다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        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];

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        // DP
        int[] dp = new int[k+1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
        // Output
        System.out.print(dp[k]);
    }
}

🔸 코드 해석 🔸

• dp는 dp[i]는 i원을 만드는 경우의 수를 저장할 배열이다.
• dp[0]은 아무 동전도 안내는 경우(공집합)가 있으므로 1이다.
  • 사실 n의 최소값이 1이기 때문에 답으로 쓰이진 않지만, 점화식 참조에 필요해서 1을 넣어야 한다.
• n가지 코인으로 만들 수 있는 수는 0을 제외하고 최소 coins[0]이므로, coins[i] ~ k 까지 값을 누적한다.
  • 해당 동전을 뺐을 때의 최적값을 현재 값에 더한다.

---

🔸 end 🔸

• 점화식을 만들기 어려워서 고민하다 점화식만 참고하고 풀었다.
• DP의 점화식 추출을 더 연습해야 할 것 같다.