문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

N = int(input())
num_arr =  [[0 for i in range(10)] for j in range(N+1)]
for i in range(10):
    num_arr[1][i] = 1

for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            num_arr[i][j] = num_arr[i-1][1]
        elif j == 9:
            num_arr[i][j] = num_arr[i-1][8]
        else :
            num_arr[i][j] = num_arr[i-1][j-1] + num_arr[i-1][j+1]
            
print(int(sum(num_arr[N][1:10]) % 1000000000))

코드 설명

각 숫자로 시작하는 계단 수의 개수를 표로 만들어보면 아래와 같다.

각 행은 수의 길이를 나타낸다.

규칙을 살펴보면 1로 시작하는 수는 전 행의 0으로 시작하는 계단 수의 개수와 2로 시작하는 계단 수의 개수의 합과 같다.

2는 전 행의 1과 3, 3은 전 행의 2와 4, … , 8은 전 행의 7과 9

예외로는 0은 전 행의 1, 9는 전 행의 8로 시작하는 계단 수의 개수와 같다.

따라서 num_arr배열의 1행에 모두 1를 넣고 입력받은 N의 값까지 for문을 돌려서 배열에 값을 업데이트한다.

길이가 N인 계단 수의 총 개수는 N행의 전체 합을 구하면 된다. (단, 0으로 시작하는 수는 없으므로 첫 번째 열은 제외하고 더해준다.)

문제출처 : baekjoon10844