백준 10844번: 쉬운 계단수 (Kotlin)

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

10844번: 쉬운 계단 수

풀이

길이가 (k-1)인 계단 수에 마지막 자리 숫자의 +1, -1한 수를 붙이면 길이가 k인 계단 수를 구할 수 있다.

ex) 12 -> 121, 123

 

이걸 점화식으로 표현하기 위해 dp[k][i]를 아래와 같이 정의하면,

dp[k][i]: 길이가 k이고, 마지막 자리 숫자가 i인 계단 수의 개수

dp[k][i] = {

               if (i == 0), dp[k-1][i+1]

               if (0 < i < 9), sum(dp[k-1][i+1]) + sum(dp[k-1][i-1])

               if (i == 9), dp[k-1][i-1]

             }

ex) 길이가 4이고 3으로 끝나는 계단 수의 개수는, 길이가 3이고 2로 끝나는 계단 수의 개수와 4로 끝나는 계단 수의 개수를 합한 값

 

위와 같이 계단 수의 길이를 기준으로 이전 항의 값으로 다음 항의 값을 표현할 수 있고, 키 포인트는 이전 길이의 계단 수들이 어떤 숫자로 끝났는지 기록하는 것이다. 그리고 0과 9로 끝나는 수들은 다른 숫자들과는 다르게 1과 8에서만 파생된다.

 

이 문제는 다이나믹 프로그래밍 유형으로, 문제 상황을 이전 값으로 다음 값을 표현할 수 있으면 해결이 가능하다. 그걸 어떻게 생각해내느냐는 어릴 때 수학을 열심히 했거나, 머리가 좋거나, 둘 다 아니라면 문제를 많이 풀어보는 수밖에 없는듯 하다.

코드

fun main(){
    val n = readLine()!!.toInt()
    var table = Array(100){IntArray(10)}

    // 한 자리 계단 수는 1~9 한 개씩
    for (i in 1..9){
        table[0][i] = 1
    }
    
    // 길이 2~n까지 n-1번 반복
    repeat(n-1){ k ->
        table[k+1][0] = table[k][1]
        table[k+1][9] = table[k][8]

        for (i in 1..8){
            table[k+1][i] = (table[k][i-1] + table[k][i+1]) % 1_000_000_000
        }
    }

    // 길이 n의 모든 계단 수의 개수를 합한다
    println(table[n-1].toList().reduce{acc, num -> (acc + num) % 1_000_000_000})
}