[BaekJoon] 11057번 오르막 수(Kotlin) 문제 풀이 [Silver 1]

문제

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

11052번: 카드 구매하기

 

어떻게 풀 것인가?

문제를 처음에 보자마자 DP가 떠오르긴 하였다.

 

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

예를 들어서, 123 -> 1233, 1234, ..., 1239

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

 

길이 k와 마지막 자리 숫자 i로 점화식 dp를 정의하면,dp[k][i]: 길이가 k이고, i로 끝나는 오르막 수

그래서 내가 정리한 점화식은 이러하다. dp[k][i] = sum( dp[k-1][j] ), (0 <= j <= i)

 

풀면서 놓쳤던점

점화식이 많이 떠오르지 않아서 처음에 많이 헤맨 문제였습니다.

 

이 문제를 통해 얻어갈 것

다이나믹 프로그래밍을 통한 해결

 

내 코드 

// 백준알고리즘 11057번 오르막 수
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val dp = Array(n + 1) { IntArray(10) }
    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 })
}

 

참고

X