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

문제

---

생각하기

---

• DP 문제이다.

• 2개씩 나눠서 암호가 될 수 있는지 파악해야 한다.

• 이 과정을 하나씩 분해해가며, 진행한다.

동작

결과

코드

---

Kotlin

Top-Down

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private const val MOD = 1_000_000
private var S = ""
private var N = 0

private lateinit var memo: IntArray

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    // 암호를 해석할 수 없는 경우에는 0을 출력한다.
    if (S[0] == '0') {
        sb.append(0)
    } else {
        sb.append(DP(N) % MOD)
    }

    return sb.toString()
} // End of solve()

private fun DP(n: Int): Int {
    if (n == 0 || n == 1) return 1

    if (memo[n] != -1) return memo[n]

    memo[n] = 0
    if (S[n - 1] > '0') {
        memo[n] = DP(n - 1)
    }

    val temp = S.substring(n - 2, n).toInt()
    if (temp in 10..26) {
        // 2개의 문자열을 합한 값이 10에서 26시이일 경우
        // 문자 하나를 만들 수 있음
        memo[n] += DP(n - 2)
    }

    memo[n] %= MOD
    return memo[n]
} // End of DP

private fun input() {
    S = br.readLine()
    N = S.length

    memo = IntArray(N + 1) { -1 }
} // End of input()

Bottom-Up

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private const val MOD = 1_000_000
private var S = ""
private var N = 0

private lateinit var memo: IntArray

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    if (S[0] == '0') {
        sb.append(0)
    } else {
        // 기저 조건
        memo[0] = 1
        memo[1] = 1

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

    return sb.toString()
} // End of solve()

private fun DP() {
    for (n in 2..N) {
        if (memo[n] != 0) continue

        if (S[n - 1] > '0') {
            memo[n] += memo[n - 1]
        }

        val temp = S.substring(n - 2, n).toInt()
        if (temp in 10..26) {
            memo[n] += memo[n - 2]
        }

        memo[n] %= MOD
    }
} // End of DP()

private fun input() {
    S = br.readLine()
    N = S.length

    memo = IntArray(N + 1) { 0 }
} // End of input()