[BOJ] 10844 쉬운 계단 수 (Python / 파이썬)

🧷 문제

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

정수 n이 주어졌을 때, 길이가 n인 모든 자리수의 차이가 1이 나는 계단수의 개수를 구하는 문제이다.

🛠 풀이

이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다.

Step 1.
 먼저 DP table을 d[자리수][끝자리 숫자] = 경우의 수로 구성한다.

Step 2.

자리수	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2

 자리수가 1일때부터 보면, 자리수가 1일때는 당연하게도 경우의 수가 1이다.
 자리수가 2일때부터는 맨 뒤에 0 또는 9가 오는 경우 특수하다. 첫번째로, 0으로 끝나는 경우 자리수 - 1의 끝자리 숫자가 1인 경우만 가능하다. 마찬가지로, 9로 끝나는 경우에는 자리수 - 1의 끝자리 숫자가 8인 경우만 가능하므로 각자 d[i][j] = d[i-1][1], d[i][j] = d[i-1][8]로 표현할 수 있다.
 끝자리 숫자가 1부터 8까지는 문제에 나와있듯이 계단수의 정의를 이용하여 차이가 1이 나도록 DP table을 구성해준다. 코드로 표현하면 d[i][j] = d[i-1][j-1] + d[i-1][j+1] 이렇게 표현할 수 있다.

Step 3.
 마지막으로 문제에서 "정답을 1,000,000,000으로 나눈 나머지를 출력한다." 라고 나와있었으므로 n자리 숫자의 모든 경우의 수의 합에서 1,000,000,000을 나눈 나머지를 출력한다.

🖊 나의 코드

def solution(x):
    d = [[0] * 10 for _ in range(101)]
    for i in range(1, 10):
        d[1][i] = 1

    for i in range(2, n+1):
        for j in range(10):
            if j == 0:
                d[i][j] = d[i-1][1]
            elif j == 9:
                d[i][j] = d[i-1][8]
            else:
                d[i][j] = d[i-1][j-1] + d[i-1][j+1]

    return sum(d[x]) % 1000000000

if __name__ == "__main__":
    n = int(input())
    print(solution(n))