[ 백준 10844 ] 쉬운 계단수 (Kotlin 풀이)

1.문제 

45656이란 수를 보자.

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

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

2. 입력

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

3. 출력

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

---

4. 포인트

1. 동적계획법을 떠올려야하며 2차원 배열을 통해 풀어야한다.
2. 점화식을 세울 수 있어야한다 
   1. [자리값 0]  DP[ i ][ j ] = DP[ i-1 ][ 1 ] 
   2. [자리값 9] -> DP[ i ][ j ] = DP[ i-1 ][ 8 ]
   3. 나머지  DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + DP[ i-1 ][ j+1 ]
3. 1,000,000,000으로 나눗셈을 저절히 해야한다.

1.  

4. 문제 풀이

DP 문제중에서 2차원 배열을 사용하는 문제가 처음이라 많이 헤맸다.

다른 사람들의 풀이를 통해 이해하게 되었으나 처음엔 도통 무슨 말인지 이해가 안되서

나같은 사람을 위해 최대한 쉽게 설명해보려고 한다.ㅎㅎ

 

[ 자세한 설명 ] 

일단 넘어 갔다가 이해가 안되면 다시 돌아와 읽어보는 것을 추천드립니다.

 

예를들어 2을 입력받아 2자리수를 형성하는 상황을 생각해보자

2자리의 계단 수중 4로 시작하는 값의 경우의 수를 생각해보면 43 ,  45 가 있을 것이다.

 

다시 3을 입력받아 3자리수를 형성하는 상황을 생각해보자

3자리의 계단 수중 5로 시작하는 값의 경우의 수를 생각해보면 543 ,  545 , 532 , 534 가 있을 것이다.

 

잘 보면 앞자리에 따라 뒷자리가 결정되고 이렇게 결정된 뒷자리수는 또 다음 뒷자리를 결정 짓는다.

앞자리가 0 , 9 일때는 뒷자리가 각각 1 , 8로 결정되고

나머지 숫자일 경우에는 그 수의 +1 / -1 한 수가 뒤자리에 올 수 있다.

 

이에 따라 자릿수와 자리값 을 각각 행,열  로 하는 배열에 그때에 경우의 수를 저장하는 배열을 만들어 보자

 

만약 이렇게 배열을 왜 만드는 것인지 이해가 안되더라도 일단 만들고 값들의 관계를 보다 보면 이해할 수 있다.

 

[자세한 설명 끝]

 

 

현재 자리수 특정 값에 대해서 그 경우의 수는 그 다음 나올 수 있는 값의 경우의 수들의 합으로 생각할 수있다.

 

앞자리가 0 , 9 일때는 뒷자리가 각각 1 , 8로 결정되고

나머지 숫자일 경우에는 그 수의 +1 / -1 한 수가 뒤자리에 올 수 있다.

 

if 자리값  == 0 -> DP[ 자리수  ][ 자리값 ] = DP[ 자리수-1 ][ 1 ] 

else fi 자리값 == 9 -> DP[ 자리수  ][ 자리값 ] = DP[ 자리수-1 ][ 8 ] 

else ->  DP[ 자리수  ][ 자리값 ] = DP[ 자리수-1 ][ 자리값-1 ] + DP[ 자리수-1 ][ 자리값+1 ]

 

의 점화식을 갖게됩니다.

 

위와 같은 접근의 흐름대로 코드를 작성하면 Top-Down 방식으로 작성할 수 있고

한번 더 생각해보면 쉽게 Bottom-Up 도 작성해볼 수 있습니다.

 

마지막으로 나눗셈에 대한 부분도 잊지말고 추가해주세요

// Top-Down

import java.io.BufferedReader
import java.io.InputStreamReader

val N = readLine()!!.toInt()
val dp = Array<Array<Int?>>(N + 1) { Array<Int?>(10) { null } }

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    dp[1][0] = 0
    for (i in 1..9) {
        dp[1][i] = 1
    }
    var result = 0

    for (i in 0..9) {
        result += recur(N, i)!!
        result %= 1000000000
    }
    println(result)
}


fun recur(num: Int, valueIdx: Int): Int? {
    if (num == 1) {
        return dp[num][valueIdx]
    }
    if (dp[num][valueIdx] == null) {
        dp[num][valueIdx] =
            when (valueIdx) {
                0 -> recur(num - 1, 1)
                9 -> recur(num - 1, 8)
                else -> recur(num - 1, valueIdx - 1)!! + recur(num - 1, valueIdx + 1)!!
            }
    }
    return dp[num][valueIdx]!! % 1000000000

 

//Bottom-Up

import java.io.BufferedReader
import java.io.InputStreamReader


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val N = kotlin.io.readLine()!!.toInt()
    val dp = Array<Array<Int?>>(N + 1) { Array<Int?>(10) { null } }

    dp[1][0] = 0
    for (i in 1..9) {
        dp[1][i] = 1
    }
    var result = 0

    for (i in 2..N) {
        for (j in 0..9) {
            dp[i][j] =
                if (j == 0) {
                    dp[i - 1][1]
                } else (if (j == 9) {
                    dp[i - 1][8]
                } else {
                    dp[i - 1][j - 1]!! + dp[i - 1][j + 1]!!
                })!! %1000000000
        }
    }
    for (i in 0..9) {
        result += dp[N][i]!!
        result %= 1000000000
    }
    println(result)
}