[BEAKJOON] 백준 10844번 : 쉬운 계단 수 - 파이썬

문제

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

10844번: 쉬운 계단 수

문제해설

45656이란 수를 보자.

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

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

 

먼저 값이 1일때를 보자

# 1 -> 9: 1, 2, 3, 4, 5, 6, 7, 8, 9

n의 값이 2일때는

# 2 -> 17: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

n의 값이 3일때는

# 3 -> : 123, 121, 101, 212, 210, 232, 234, 321, 323, 343, 345,
# 456, 454, 4,,~
# 789, 787, 767, 765
# 987, 989,

그렇다면, 확인되는 게 있다.

앞의 리스트에서 뒤의 자리가 1인 갯수가 다음 번의 뒤의 0인 갯수가 되고,

앞의 리스트의 뒤의 자리가 8인 갯수가 다음 번의 9인 갯수가 된다.

나머지는 이전의 리스트에서 해당 숫자 앞뒤의 값을 더해주는 개수의 값이 된다.

 

정답 코드

num = int(input())

num_list = [[0]*10 for _ in range(num)]
num_list[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

zero_nine_result_list = list()
result_list = list()

zero_nine_result_list.append(1) # 0, 9
result_list.append(8)
zero_nine_result_list.append(2) # 10, 89
result_list.append(15)
#zero_nine_result_list.append(2) # 210, 989, 789
for i in range(1, num):
    num_list[i][0] = num_list[i-1][1]
    num_list[i][9] = num_list[i-1][8]
    for j in range(1, 9):
        num_list[i][j] = num_list[i-1][j-1] + num_list[i-1][j+1]

print(sum(num_list[num-1])%1000000000)