백준 2293번
https://www.acmicpc.net/problem/2293

문제

---

생각하기

---

• DP 문제이다.

  • memoization을 활용하여 최적화를 해야 한다.

• Bottom Up의 방법으로만 구현이 가능하다.

  • 공간 복잡도 때문에 2차원 배열을 생성할 수 없다.

• memo[index - 동전의 가치] 부분을 잘 생각해야 한다.

동작

private fun DP() {

    for (i in 1..N) {
        for (j in 0..K) {
            if (j - money[i] >= 0) {
                memo[j] += memo[j - money[i]]
            }
        }
    }

} // End of DP

Bottom Up 방식이므로 0원부터 K까지 금액을 반복문으로 탐색하며 금액을 만든다.
memo[K] 까지 도달하는 가짓수를 모두 저장하는 방식으로 최적화를 했다.

코드

---

Kotlin

import java.util.*
import java.io.*
import java.lang.StringBuilder

private var N = 0
private var K = 0

private val memo = IntArray(10_001)
private val money = IntArray(101)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 동전의 개수
    K = st.nextToken().toInt() // 목표

    for (i in 1..N) {
        money[i] = br.readLine().toInt()
    }

    memo[0] = 1
    DP()
    sb.append(memo[K])

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun DP() {

    for (i in 1..N) {
        for (j in 0..K) {
            if (j - money[i] >= 0) {
                memo[j] += memo[j - money[i]]
            }
        }
    }

} // End of DP