[백준/Kotlin] 동전 바꿔주기(2624)

🔗 문제 링크

백준 - 다이나믹 프로그래밍 | 동전 바꿔주기(2624)

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

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

20 = 10×2
20 = 10×1 + 5×2
20 = 10×1 + 5×1 + 1×5
20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.

---

✔️ 소요된 시간

4~50분

---

✨ 문제 풀이

DP 점화식을 고민하는 데에 시간을 좀 사용했습니다!

 

고민 1️⃣ : [금액] - 0원부터 T원까지의 경우의 수를 순차적으로 구할 수 있을까?

T = t1 + t2일 때,
(T원을 만드는 경우의 수) = (t1원을 만드는 경우의 수) * (t2원을 만드는 경우의 수)라는 식을 발견해서 이걸 활용해보려고 했지만…
(t1원을 만드는 경우의 수), (t2원을 만드는 경우의 수)는 어떻게 구할 수 있는지 생각이 안 나서 해당 식은 활용을 못 했습니다 🥺

 

고민 2️⃣ : [동전 개수][금액] - 동전 1개로 만들 수 있는 금액부터 N개까지 순차적으로 구해볼까?

N개의 동전으로 M원을 만들 수 있는 경우의 수를 작은 것부터 구해나갈 수 있지 않을까 했지만!
동전의 금액이 다양해서, 동전 N개라고 해도 그 구성이 다양하고 그걸 구할 방법이 생각보다 복잡해질 것 같았습니다.

그래서 구현 복잡도를 줄이기 위해, 한 종류의 동전을 먼저 1개부터 모두 사용하는 방법을 계산하고,
그 다음 종류의 동전을 고려하는 방식으로 해결해볼 수 있지 않을까?? 하는 생각이 들었습니다

 

Solution ✅ : [몇 번째 동전까지 체크했는지][금액]

결과적으로 dp의 index를 [몇 번째 동전까지 체크했는지][금액]로 둬야했는데, 이때 점화식을 구해낸 과정을 설명해보겠습니다

 

예를 들어 k번째 동전이 100원이고 3개가 있을 때 1000원을 만들려고 한다면 / dp[k][1000]

100원을 0개, 1개, 2개, 3개씩 쓰는 경우의 수가 나올 수 있습니다.

 

0개 ➡️ k-1번째 동전까지 조합했을 때 1000원이 나왔어야 함 / dp[k-1][1000 - 100 * 0]
1개 ➡️ k-1번째 동전까지 조합했을 때 900원이 나왔어야 함 / dp[k-1][1000 - 100 * 1]
2개 ➡️ k-1번째 동전까지 조합했을 때 800원이 나왔어야 함 / dp[k-1][1000 - 100 * 2]
3개 ➡️ k-1번째 동전까지 조합했을 때 700원이 나왔어야 함 / dp[k-1][1000 - 100 * 3]

 

dp[k][1000] = dp[k-1][1000 - 100 * 0] + dp[k-1][1000 - 100 * 1] + dp[k-1][1000 - 100 * 2] + dp[k-1][1000 - 100 * 3]

 

결국 1000은 t이고, 100은 동전의 금액 p, 3은 동전의 개수 n이기 때문에

dp[k][t] = dp[k-1][t - p * 1] + ... + dp[k-1][t - p * (n - 1)] + dp[k-1][t - p * n]
즉, dp[k][t] += dp[k-1][t - p * i]라는 식이 도출됩니다. 🥳

 

for(k: Int in 1..K) { // 현재 사용하려는 동전 번호
    dp[k - 1][0] = 1
    for(t: Int in 1..T) { // 만드는 금액
        for(n: Int in 0..coins[k - 1][1]) { // k번째 동전의 개수
            if(t < coins[k - 1][0] * n) break
            dp[k][t] += dp[k - 1][t - coins[k - 1][0] * n]
        }
    }
}

 

해당 부분을 코드로 보면 위와 같습니다!
0원을 만드는 경우의 수는 항상 1이라고 했기 때문에 해당 값을 넣어주고,
동전을 순서대로 1원부터 T원까지 만들 수 있는 경우의 수를 계산합니다.
동전을 0개부터 n개 쓰는 값을 구해서 누적해줍니다.

---

🔥 최종 코드

사용 언어: Kotlin

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

fun main() {
  // ✅ Input
  val br = BufferedReader(InputStreamReader(System.`in`))

  var T = br.readLine().toInt() // 지폐의 금액
  var K = br.readLine().toInt() // 동전의 가지 수

  var coins = Array(K, {Array(2, {0})})

  // 동전의 금액과 개수
  for(i: Int in 0..K-1) {
    val st = StringTokenizer(br.readLine())
    coins[i][0] = st.nextToken().toInt()
    coins[i][1] = st.nextToken().toInt()
  }

  // ✅ Solve
  // [몇 번째 동전까지 사용했는지][만드는 금액]
  var dp = Array(K + 1, {Array(T+1, {0})})
  for(k: Int in 1..K) { // 현재 사용하려는 동전 번호
    dp[k - 1][0] = 1
    for(t: Int in 1..T) { // 만드는 금액
      for(n: Int in 0..coins[k - 1][1]) { // k번째 동전의 개수
        if(t < coins[k - 1][0] * n) break
        dp[k][t] += dp[k - 1][t - coins[k - 1][0] * n]
      }
    }
  }

  // ✅ Output
  print(dp[K][T])
}

 

 

1-jung0115 by jung0115 · Pull Request #120 · AlgoLeadMe/AlgoLeadMe-4