[Kotlin][Algorithm] 11057 - 오르막 수

문제 요약

오르막 수는 수의 자리가 오름차순을 이루는 수를 의미하며, 인접한 수가 같아도 오름차순으로 간주한다. 길이가 N인 오르막 수의 개수를 구하는 것이 이 문제의 목표입니다.

문제 접근

다이나믹프로그래밍

이 문제는 하위 결과를 통해 복잡한 문제를 해결하는 DP를 이용하는게 KEY이다.

만약 N자리수의 모든 수를 구해서 오름 차순을 검사한다면

9^N 개의 수에 대해서 길이 N번의 반복을 통해 구해야 하므로 시간 복잡도가 매우 커진다.

이 문제 같은 경우는 이전 숫자의 마지막 수보다 크거나 같은 숫자를 추가하기만 하면 된다.

그럼 만약에 2자리수인데 마지막 자리수가 2인 것의 개수는 몇일까

02, 12, 22가 있다.
마지막 2를 다시 빼보면 0,1,2가 된다.
이제 패턴이 보인다. 이전 자리의 숫자보다 크거나 같은 숫자를 추가하면 된다는 거다.

즉 이 말은 i번째 자리수의 마지막 숫자가 j번째 숫자인 것의 개수는 i - 1번째 자릿수에서 j보다 작거나 같은 것들의 개수의 합이라는 것이다.

코드

주석을 보면 점화식이 이해가 갈 것이다.
주의할점은 문제에 나와있는 10007로 모듈러 연산을 적용시키는 것.

const val MOD = 10007

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val dp = Array(n + 1) { IntArray(10) }
    
    // 초기 조건 자릿수가 1이면 본인만 있다.
    dp[1].fill(1)
    
    // 길이 
    for (i in 2 .. n) {
        // 끝나는 수
        for (j in 0 until 10) {
            // 이전 자릿수의 끝나는 수
            for (k in 0 .. j){
                dp[i][j] += dp[i -1][k]
                dp[i][j] %= MOD
            }
        }
    }

    println(dp[n].sumOf { it } % MOD)
}

배운점

이차원 다이나믹프로그래밍 점화식