[백준] 10844 : 쉬운 계단 수 (파이썬 / Python)

---

쉬운 계단 수

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

10844번: 쉬운 계단 수

---

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

---

코드

n = int(input())
d = [[0] * 10 for _ in range(n+1)]

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 1 <= j <= 8:
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
        else:
            d[i][j] = d[i-1][8]
            
print(sum(d[n]) % 1000000000)

풀이

이 문제에서 풀어야 하는 것은 1) 입력으로 주어진 길이 N에 대해 2) 인접한 수를 파악하여 3) 해당 길이의 계단 수가 몇 개 있는지 구하는 것이다. 

문제가 주어졌을 때 길이 N에 따른 규칙을 찾아 점화식을 구성하고자 하였고, 이 과정에서 한 가지 규칙을 찾아내었다.

n = 1일 때는 1, 2, 3, 4, 5, 6, 7, 8, 9로 계단 수는 9개이고,

n = 2일 때에는 맨 뒤에서 한 자리 앞의 수가 1인 경우에는 0, 2가, 2인 경우에는 1, 3이 , ... , 8인 경우에는 7, 9가, 즉, 2가지의 경우의 수가 올 수 있다. 하지만 맨 뒤에서 한 자리 앞의 수가 9인 경우에는 8만 올 수 있다. (물론, n = 1의 경우 첫 자리수가 0이 될 순 없지만 n > 2인 경우) 맨 뒤에서 한 자리 앞의 수가 0인 경우에는 1만 올 수 있다.

이를 점화식으로 표현하기 위해서는 계단 수(경우의 수)를 저장할 2차원의 배열이 필요하다고 판단했다. 그 이유는 1) 입력으로 주어진 길이 N, 2) 맨 마지막 자리의 숫자에 대해 3) 계단 수가 몇 개 각각 저장해주어야 각 단계에서 활용할 수 있기 때문이다. 즉, d[자리수][맨 마지막 자리의 숫자]로 표현할 수 있다.