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

문제 내용

문제

45656이란 수를 보자.

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

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

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력	예제 출력
1	9
2	17

문제 풀이

항상 생각하는건데 DP는 아이디어만 떠올리면 그뒤로는 쉬운거 같다.. 문제는 그 아이디어를 떠올리기 힘들다는 것.. 

이 문제는 인접한 자리의 차이가 1이다. 가 힌트라고 볼 수 있다. 각 자리를 도는데 이때 첫자리를 제외하곤, 들어갈 수 있는 값이 0부터 9까지 이다. 

사실 아래 코드를 보면 코드와 내용 자체는 어렵지 않다!! 주의할 점은 오버플로우가 나지 않게 숫자의 범위를 설정하는 것

</>̆̈ 코드

fun main() {
    val n = System.`in`.bufferedReader().readLine().toInt()
    val stair = Array(n) {LongArray(10) {1L} }; stair[0][0] = 0L
    for (i in 1 until n) { // i = 각 자릿수
        for (j in 0 until 10) { // j = 각 자리에 들어갈 수 있는 숫자
            stair[i][j] = when(j) {
                0 -> stair[i-1][1]
                9 -> stair[i-1][8]
                else -> (stair[i-1][j-1] + stair[i-1][j+1])
            } % 1_000_000_000
        }
    }
    print(stair[n-1].sum() % 1_000_000_000)
}

링크

10844번: 쉬운 계단 수