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

백준 문제 주소 https://www.acmicpc.net/problem/10844

문제

45656이란 수를 보자.

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

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

입력

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

2

출력

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

17

---

지금까지 푼 이번 시리즈 문제 중에 규칙 찾기가 제일 어려운 것 같다...
처음부터 9개의 종류로 시작해서 경우의 수를 세기 시작한다면 너무 복잡해진다.
한 자리 수의 경우에는 1, 2, 3, 4, 5, 6, 7, 8, 9가 있고,
두 자리로는 10, 12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21로 총 17개가 있다.
세 자리로는 123, 234, 345, 456, 567, 678, 789를 뒤집은 것 + 210까지 포함해서 15개
121, 232, 343, 454, 565, 676, 787, 898에 중간 숫자가 하나 작은 것 + 989도 계산해서 17개
총 32개

위의 것들에서 규칙을 찾는다면?

위의 표는 길이당 시작하는 숫자의 수를 정리한 것이고, 아래의 표는 길이당 끝나는 수를 정리한 것이다.
생각해보면 어떤 N자리 수의 계단 수가 있다고 하면 그것은 N-1자리 계단 수에 적절한 마지막 숫자를 붙인 것과 같다.
즉, 3자리 수의 3으로 끝나는 계단 수의 개수(3)는 2자리 수의 2로 끝나는 계단 수(1)와 2자리 수의 4로 끝나는 계단 수(2)의 합과 같다.

이를 식으로 표현하면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]인 것이다.

하지만 그것만으로는 구현을 할 수 없었다...
길이가 3일때, 3부터 7까지는 끝나는 수의 개수가 4개씩이다. 하지만 0부터 2까지 그리고 8, 9는 4개가 되지 못한다.
이는 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]라는 식을 생각해보면 0과 9는 더 적은 수 또는 더 큰 수가 없는 경우 때문에 연산 과정에서 한쪽 값만을 받아오기 때문이다.

Python 풀이

n = int(input())
arr = [[0 for _ in range(10)] for _ in range(n + 1)]

arr[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n+1):
    arr[i][0] = arr[i-1][1]
    arr[i][9] = arr[i-1][8]
    
    for j in range(1, 9):
        arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]

print(sum(arr[n]) % 1000000000)

Kotlin 풀이(실패)

import java.io.*

fun main(args: Array<String>)
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n+1){ Array(10){0} }

    for (i in 1..9) {
        arr[1][i] = 1
    }

    for (i in 2..n) {
        arr[i][0] = arr[i-1][1]
        arr[i][9] = arr[i-1][8]

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

    println(arr[n].sum() % 1000000000)
}

Kotlin 풀이(성공)

import java.io.*

fun main()
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n+1){ Array(10){0} }

    for (i in 1..9) {
        arr[1][i] = 1
    }

    for (i in 2..n) {
        arr[i][0] = arr[i-1][1]
        arr[i][9] = arr[i-1][8]

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

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

처음 파이썬 코드를 그대로 코틀린 코드로 문법만 수정했는데, 기본 내용은 같은데 계속 틀리기만 했다. 구글링을 시도했더니 한 블로그에서

출력 : 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력
이런 출력 조건이 있을 경우, DP테이블에 N이전 값들을 계산하는 과정에서 매번 값들에 1,000,000,000 나머지 연산을 취해줘야 최종 결과값이 바르게 구해짐.
https://bada744.tistory.com/m/86

라는 내용을 봤다.
하지만 배열의 sum() 부분의 코드도 틀렸다고 나왔다. 이 부분에 대해서는 정확히 아는데 Int 타입의 크기를 초과해서 문제가 생긴 것이다. 처음에는 sum() 메소드가 파이썬의 sum()과 기능이 다르게 동작하는 것인지를 의심했다. 하지만 문제는 그게 아니였다.

따라서 다른 블로그를 구글링하며 찾아낸 저 정보의 이유도 자료형에 있을 것이라고 추정했다.

import java.io.*

fun main()
{
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val arr = Array(n+1){ Array(10){0L} }

    for (i in 1..9) {
        arr[1][i] = 1L
    }

    for (i in 2..n) {
        arr[i][0] = arr[i-1][1]
        arr[i][9] = arr[i-1][8]

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

    println(arr[n].sum() % 1000000000)
}

추정에 따라서 코드를 수정하고 백준에 제출해보니 정답이라고 나왔다. 오늘 의문을 남겨두지 않고 다 알게되어 정말 좋다!