[2023-04-23] 10844 쉬운 계단 수 (Kotlin)

 

문제 링크: https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

저 스스로 풀지 못했습니다.

 

다른 분의 풀이를 가지고 왔습니다.

 

import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    var start = 1
    for (index in 0 until n - 1){
        start *= 10
    }
    var end = 1
    for (index in 0 until n){
        end *= 10
    }

    val dp = Array(n+1){ Array(10){0} }

    // 0
    dp[1][0] = 0

    // 1 ~ 9
    for(j in 1 until 10){
        dp[1][j] = 1
    }

    for(i in 2 until n+1){
        for(j in 0 until 10){
            when(j){
                0 -> dp[i][j] = dp[i-1][1] // 0은 1 뒤에만 추가할 수 있음
                9 -> dp[i][j] = dp[i-1][8] // 9는 8 뒤에만 추가할 수 있음
                else -> dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1]) % 1000000000
            }
        }
    }

    var sum = 0L
    dp[n].forEach { sum += it }
    sum %= 1000000000
    println(sum)
}