10844. 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

인접한 모든 자리의 수가 1 차이 나는 수 가 계단수이다. (예: 45656)

0으로 시작할 수는 없다.

 

d[n][a] : 길이가 n인 계단수중 끝 숫자가 a인 계단수의 총 개수

 

즉 길이가 n인 계단수의 총 개수 

d[n] = d[n][0] + d[n][1] + d[n][2] + ... + d[n][9]

 

n = 1 일때

1 

2

3

4

5

6

7

8

9

 

n = 2 일때

10

21

12, 32

23, 43

34, 54

45, 65

56, 76

67, 87

78, 98

89

 

n = 3일때

210

121, 121, 321

212, 232, 432

123, 323, 343, 543

234, 434, 454, 654

345, 545

456, 656 ...

 

보면 알듯이 계단 사이의 차는 1이면 되기 때문에 내려오는 계단일수도 있고 올라가는 계단 일 수 도 있다.

그래서 d[n][a] = d[n-1][a-1] + d[n-1][a+1]

 

그런데 위에서 보면 맨 뒤 자리가 0일때는 예를들어 10 이면 그후 내려가는 계단이 있을 수 없고 올라가는 계단만 있을 수 있다. 그래서 d[n][0] = d[n-1][1]

// n = 2일때 21(d[n-1][1])이 210(d[n][0])이 됨

 

마찬가지로 맨 뒤 자리가 9이면 예를들어 89 이면 그 후 올라가는 계단이 있을 수 없고 내려가는 계단만 있을 수 있다.

그래서 d[n][9] = d[n-1][8]

 

이 두가지 경우를 예외처리를 해줘야 한다.

d = [[0] * 10 for i in range(101)]

for i in range(10):
    d[0][i] = 0

d[1][0] = 0  # base
for i in range(1, 10, 1):  # 1자리의 개수는 다 1
    d[1][i] = 1


def dp(a, b):
    for i in range(10):
        if b == 0:  # 맨 뒤 자리가 0이면 예외처리
            d[a][b] = d[a-1][1]
        elif b == 9:  # 맨 뒤 자리가 9면 예외처리
            d[a][b] = d[a-1][8]
        else:
            d[a][b] = d[a-1][b-1] + d[a-1][b+1]

        return d[a][b]


n = int(input())  # n : 문자 길이

for i in range(2, n+1, 1):  # 2 부터 n까지
    for j in range(10):
        d[i][j] = dp(i, j)

res = 0
for i in range(10):
    res += d[n][i]

print(res % 1000000000)