[백준] 10844 쉬운 계단 수 (Kotlin 코틀린)

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

10844번: 쉬운 계단 수

문제 설명

5656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

---

풀이 과정

이 문제는 단계마다의 규칙을 찾아 점화식을 세워 구현하는 DP 문제이다.

 

길이 1짜리 계단을 생각해보면,

1 2 3 4 5 6 7 8 9 총 9개의 계단이 있다.

 

길이 2짜리 계단을 생각해보면,

10 12 21 23 32 34 43 45 ... 87 89 98 로 총 17개가 있다.

 

그렇다면 길이 3짜리 계단은,

101 121 123 212 210 232 234 ... 789 787 898 987 989 가 있다.

 

여기서 규칙을 찾아보자.

끝자리가 0이나 9라면 더 늘릴 수 있는 수가 없기 때문에 하나만 더 추가로 만들 수 있다.

 

예를 들어, 10 같은 경우 끝자리 0에 1을 추가한 101 만을 만들 수 있다.

하지만, 끝자리가 0이 아닌 21 같은 경우는 1을 추가한 212나 1을 뺀 210을 만들 수 있게 된다.

 

이를 이용하면, 다음과 같은 코드를 작성할 수 있다.

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()

    val dp = Array(101) { IntArray(10) }
    dp[1][0] = 0
    for(i in 1 until 10) {
        dp[1][i] = 1
    }

    for(i in 2 until n+1) {
        for(j in 0 until 10) {
            when(j) {
                0 -> dp[i][j] = dp[i-1][1]
                9 -> dp[i][j] = dp[i-1][8]
                else -> dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
            }
        }
    }

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

}

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !