(Kotlin) 백준 11057 - 오르막 수

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

11057번: 오르막 수

 

풀이

백준 10844번 쉬운 계단 수와 거의 같은 문제다. (https://best-human-developer.tistory.com/14)

 

k-1 길이의 오르막 수에서 마지막 수보다 크거나 같은 수를 이어 붙이면 길이가 k인 오르막 수를 구할 수 있다.

ex) 123 -> 1233, 1234, ..., 1239

이렇게 수의 길이 k에 대해 직전 항으로 다음 항을 만들 수 있으므로 다이나믹 프로그래밍으로 문제를 해결할 수 있다.

 

길이 k와 마지막 자리 숫자 i로 점화식 dp를 정의하면,

dp[k][i]: 길이가 k이고, i로 끝나는 오르막 수

dp[k][i] = sum( dp[k-1][j] ), (0 <= j <= i) 

 

 

코드

fun main(){
    val n = readLine()!!.toInt()
    val dp = Array(n+1){IntArray(10)}
    
    // 길이가 1이고 i로 끝나는 오르막수
    for (i in 0 until 10){
    	dp[1][i] = 1
    }

    // 길이 2~n까지 n-1번 반복
    for (k in 2..n){
    
        for (i in 0..9){
        	for (j in 0..i){
            	dp[k][i] = (dp[k][i] + dp[k-1][j]) % 10_007
            }
        }

    }

    println(dp[n].toList().reduce{acc, num -> (acc + num) % 10_007})
}