백준|10844번|쉬운 계단 수

문제설명
계단 수는 45656처럼 인접한 모든 자리의 차이가 1인 수라고 할 때, 길이가 N인 계단 수의 개수를 구하는 문제입니다.(0으로 시작하는 수는 계단수가 아닙니다.)

작동 순서
1. 길이 N을 입력받습니다.
2. 길이가 i일때 j로 시작하는 계단 수의 개수를 저장하는 이차원배열을 생성해줍니다.
3. 0으로 시작하는 계단 수의 개수는 i-1의 길이의 1로 시작하는 계단 수의 개수와 같습니다.
4. 1부터 8로 시작하는 계단 수의 개수는 i-1의 길이의 n-1과 n+1로 시작하는 계단 수의 개수의 합입니다.
5. 9로 시작하는 계단 수의 개수는 i-1의 길이의 8로 시작하는 계단 수의 개수와 같습니다.
6. 위 연산을 반복해서 수행한뒤 길이 N인 계단수의 1부터 9까지의 개수의 합계를 출력합니다.

소스코드

n = int(input())
memo = [[0 for _ in range(10)] for _ in range(n)]
for i in range(10):
    memo[0][i] = 1
for i in range(1, n):
    memo[i][0] = memo[i-1][1]
    for j in range(1, 9):
        memo[i][j] = memo[i-1][j-1]+memo[i-1][j+1]
    memo[i][9] = memo[i-1][8]
print(sum(memo[n-1][1:]) % 1000000000, end="")

후기
처음 보기에는 복잡해보였지만 수들의 규칙만 찾고나면 쉽게 풀 수 있는 문제인것 같습니다.