[백준] / [Python] / [10844] 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

---

하나씩 적어가며 원리를 파악 후 적용하였습니다.

N = int(input())

DP = [[1] * 9 for _ in range(N)]

for i in range(1, N):
    for j in range(9):
        if j == 0:
            if i < 2:
                DP[i][j] = DP[i-1][j+1] + 1
            else:
                DP[i][j] = DP[i-1][j+1] + DP[i-2][j]
        elif j == 8:
            DP[i][j] = DP[i-1][j-1]
        else:
            DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]
    
print(sum(DP[N-1]) % 1000000000)
    
# 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
# 10 12 / 21 23 / 32 34 / 43 45 / 54 56 / 65 67 / 76 78 / 87 89 / 98
# 101 121 123 / 212 210 232 234 / 321 323 343 345  ...  / 876 878 898 / 989 987
# 1010 1012 1210 1212 1232 1234 / 2101 2121 2123 2321 2323 2343 2345 / ... / 9876 9878 9898
# 10101 10121 10123 102