[10844] 쉬운 계단 수 - Python

/* 문제 */
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

dp 문제다. 

우선 N=1일 때부터 생각을 해보면, 길이가 1인 계단 수는 총 9개이다. N=2일 때는 N=1일 때 만들어진 수 뒤에 한 자리를 더 붙이는 것이라고 생각할 수 있다. 앞의 자릿수보다 1 크거나 1 작아야 하므로 N=1일 때의 경우의 수 * 2로 계산할 수 있는데, 앞의 자릿수가 0이거나 9일 경우에는 각각 1, 8 이외의 수는 불가능하다. 따라서 (N=1일 떄의 경우의 수) * 2 - 2로 계산한다.

이 과정을 일반화 해보면 N=i일 때의 경우의 수는 (N=i-1일 때의 경우의 수) * 2 - (앞의 자리의 0, 9의 개수)다. 따라서 현재 계산하는 자리의 바로 앞에 어떤 수들이 올 수 있는지, 이전 단계의 계산 결과를 저장해야 하는 것이다.

따라서 10*n 크기의 이차원 리스트 dp를 선언한 후 dp[i][j]에는 N=i일 때 가능한 일의 자리 수의  개수(j의 개수)를 저장한다. 예를 들어 N=2일 때 일의 자리에 올 수 있는 수는 0,2,1,3,2,4,3,5,4,6,5,7,6,8,7,9,8이다(N=1일 때의 일의 자리를 기반으로 계산). 따라서 dp[1][0] = 0, dp[1][1] = 1, dp[1][2] = 2 ... 로 저장된다. j는 이전 단계의 j-1 개수와 j+1 개수를 더해서 계산하고, j가 0, 9일 때는 이전 단계의 1의 개수와 8의 개수로 처리한다. 

위 과정을 거치면 dp의 마지막 요소에는 최종 단계의 일의 자리 경우의 수가 각각 저장된다.

# 정답 코드
n = int(input())
dp = [[0]*10 for _ in range(n)]
dp[0] = [0,1,1,1,1,1,1,1,1,1]
for i in range(1, n):
    dp[i][0] += dp[i-1][1]
    for j in range(1,9):
        dp[i][j] += dp[i-1][j-1] + dp[i-1][j+1]
    dp[i][9] += dp[i-1][8]
print(sum(dp[-1]) % 1000000000)