[백준] 10844번: 쉬운 계단 수

문제

• https://www.acmicpc.net/problem/10844

풀이

• 메모이제이션

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val dp = Array(101) { LongArray(10) { 0 } }
    for (i in 1..9) {
        dp[1][i] = 1
    }
    for (i in 2..n) {
        for (j in 0..9) {
            when (j) {
                0 -> dp[i][j] = dp[i - 1][1] % 1000000000
                9 -> dp[i][j] = dp[i - 1][8] % 1000000000
                else -> dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000
            }
        }
    }
    val result = dp[n].sum()
    bw.write("${result % 1000000000}")
    bw.close()
    br.close()
}

더 좋은 풀이 방법 있으면 댓글 달아주세요!

질문

• Int 로 풀이했을 때 제한범위를 초과해서 통과를 하지 못하는데, 제한 범위를 통과하는 기준을 어떻게 알 수 있는지 궁금하다.