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

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

10844번: 쉬운 계단 수

 

난이도 : 실버 1
태그 : 다이나믹 프로그래밍

 

 

설명

다이나믹 프로그래밍을 응용할 수 있겠는데요.

 

XXXX7 라는 계단 수를 만들려면, 바로 직전 계단수는 뭘까요?

바로 XXX6, XXX8 입니다.

직전 값과 1만큼 차이가 나면 되는 것이죠.

즉, XXXX7이 될 수 있는 경우의 수는 XXX6의 경우의 수와 XXX8의 경우의 수를 더한 것과 같습니다.

 

XXXX7는 5자리, 현재 값은 8 입니다.

이를 dp[자리 수(i)][값(j)] 으로 나타내면,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 점화식을 도출할 수 있습니다.

 

단, 현재 값이 0 또는 9일 경우 예외를 처리해줘야 합니다.

0이 되는 경우의 수는 직전 값이 1인 경우,

9가 되는 경우의 수는 직전 값이 8인 경우밖에 없기 때문입니다.

 

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val div = 1000000000L
    val n = readLine().toInt()

    val dp = Array(n) { Array(10) { 0L } }

	// 1 자리수 일 때는 모두 경우의 수가 1가지 밖에 존재하지 않음
    for (i in 1..9) dp[0][i] = 1

    for (i in 1 until n) {
        dp[i][0] = dp[i - 1][1] // 0이 되는 경우는 직전 값이 1인 경우 밖에 없음
        dp[i][9] = dp[i - 1][8] // 9가 되는 경우는 직전 값이 8인 경우 밖에 없음

        for (j in 1..8) {
            dp[i][j] += dp[i - 1][j - 1]
            dp[i][j] += dp[i - 1][j + 1]
            dp[i][j] %= div
        }
    }

    println(dp[n - 1].sum() % div)
}

 

 

 

후기

다이나믹 프로그래밍. 재밌지만 어렵습니다.