[백준] 10844. 쉬운 계단 수 (Kotlin)

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

 

 

풀이

// [백준] 10844. 쉬운 계단 수 (Kotlin)

import java.util.*

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    // dp[i][j] => 길이가 i일때 마지막 숫자가 j인 수의 갯수
    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)
}

점화식을 세워 문제를 해결해야 한다.

 

n = 1일 때 

1~9 , 9개

 

n = 2

n=1 의 결과에 작은 수를 붙일 때 10 21 32 43 54 65 76 87 98 => 9개

n=1 의 결과에 큰 수를 붙일 때    12 23 34 45 56 67 78 89 => 8개

=> 17개

 

의 형태로 이루어진다.

끝자리가 0이면 추가할 수 있는 수는 1 뿐이고

끝자리가 9이면 추가할 수 있는 수는 8 뿐이다.

나머지의 경우엔 -1, +1 두가지를 추가할 수 있다.

 

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
}

따라서 위와 같은 점화식을 완성할 수 있다.