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

문제

---

생각하기

---

• DP 문제이다.
  • 생각보다 식을 세우는 게 많이 어려웠다...

동작

코드

---

Kotlin

Top Down

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0L
private var memo = LongArray(36)


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

    input()
    memo[0] = 1

    sb.append(DP(N))

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

private fun DP(num: Long): Long {
    if (memo[num.toInt()] > 0) return memo[num.toInt()]

    var res = 0L
    for (i in 0 until num) {
        res += DP(i) * DP(num.toInt() - (i + 1))
    }

    memo[num.toInt()] = res
    return memo[num.toInt()]
} // End of DP

private fun input() {
    N = br.readLine().toLong()
} // End of input

Bottom Up

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0L
private val memo = LongArray(36)

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

    input()
    memo[0] = 1

    DP()
    sb.append(memo[N.toInt()])

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

private fun DP() {

    for (i in 1..N) {
        var idx = i - 1
        memo[i.toInt()] = 0

        for (j in 0 until i / 2) {
            memo[i.toInt()] = memo[i.toInt()] + (memo[j.toInt()] * memo[idx--.toInt()])
        }

        memo[i.toInt()] = memo[i.toInt()] * 2L

        if ((i % 2).toInt() != 0) {
            memo[i.toInt()] = memo[i.toInt()] + (memo[(i / 2).toInt()] * memo[(i / 2).toInt()])
        }
    }

} // End of DP

private fun input() {
    N = br.readLine().toLong()
} // End of input