문제 링크 (opens new window)

풀이

1. DP 테이블 정의가 너무 어렵다..
2. dp[i][j]: i번째 자릿수의 숫자가 j일때까지 총 경우의 수 합
3. j가 0일때는 1에서밖에 못오고, 9일때난 8에서밖에 못오므로 해당 경우의 수 고려
4. 모듈러 법칙 적용

import Foundation

let N = Int(readLine()!)!
var dp: [[Int]] = .init(repeating: .init(repeating: 0, count: 10), count: 101)
var sum = 0
let mod = 1_000_000_000

if N == 1 {
    print(9)
    exit(0)
}

for i in 1...9 {
    dp[1][i] = 1
}

for i in 2...N {
    dp[i][0] = dp[i-1][1] % 1_000_000_000
    dp[i][9] = dp[i-1][8] % 1_000_000_000
    for j in 1...8 {
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1_000_000_000
    }
}

print(dp[N].reduce(0, +) % 1_000_000_000)