Today I Learned

오늘은 백준 골드로 올라가서 5단계 문제를 풀었다!

계단 수

백준 1562 https://www.acmicpc.net/problem/1562

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

• 입력
  10
• 출력
  1

문제 풀이

• bottom up 방식으로 DP를 사용해 아래서부터 시작해 길이가 1인 계단 수를 구하고 반복해서 원하는 길이의 계단 수를 찾는 방식으로 문제를 풀었다.

1. 우선 나머지 구할 때 쓸 MOD = 1_000_000_000를 정의해두고 입력을 받는다.

2. dp 배열을 3차원으로 나눠서 정리한다. dp[i][j][k]는 길이가 i고 마지막 숫자가 j면서 j를 포함한 숫자 집합이 k인 계단 수를 의미한다. k는 이진수이고 j번째 비트가 1이면 해단 숫자가 계단 수에 포함되었다는 것을 의미한다.

3. Bottom-Up 방식으로 길이가 2 이상인 계단 수를 구한다. j가 0보다 큰 경우, 현재 자릿수가 j이고 j를 포함한 숫자 집합이 k인 계단 수는 이전 자릿수에서 j-1인 경우의 계단 수와 합친다. j가 9보다 작은 경우도 동일하게 처리한다.

4. 마지막으로 길이가 n이고 마지막 숫자가 j인 계단 수를모두 합해 겨로가를 계싼한다. 이 결과를 mod로 나눈 나머지를 출력하면 완료!

Kotlin 코드

fun main() {
    val MOD = 1_000_000_000
    val n = readln().toInt()

    val dp = Array(n + 1) { Array(10) { IntArray(1 shl 10) } }

    for (j in 1..9) {
        dp[1][j][1 shl j] = 1
    }

    for (i in 2..n) {
        for (j in 0..9) {
            for (k in 0 until (1 shl 10)) {
                if (j > 0) {
                    dp[i][j][k or (1 shl j)] = (dp[i][j][k or (1 shl j)] + dp[i - 1][j - 1][k]) % MOD
                }
                if (j < 9) {
                    dp[i][j][k or (1 shl j)] = (dp[i][j][k or (1 shl j)] + dp[i - 1][j + 1][k]) % MOD
                }
            }
        }
    }

    var result = 0
    for (j in 0..9) {
        result = (result + dp[n][j][(1 shl 10) - 1]) % MOD
    }

    println(result)
}