BOJ 10844 쉬운 계단 수

https://www.acmicpc.net/problem/9471
시간 1초, 메모리 128MB
input :

• N ( 1 <= N <= 100)

output :

• 정답을 1,000,000,000으로 나눈 나머지를 출력

조건 :

• 45656
• 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수 (0으로 시작 불가능)
• 수의 길이가 N인 계단 수가 몇 개??

---

어떠한 숫자가 9가 아닌 이상 계단 수로 가능한 것은 2가지 이다.

n -> n - 1 / n + 1

그러면 이것을 어떻게 리스트로 나타낼 것인가?
그냥 숫자를 곱하거나 더해서 만드는 건 불가능 할 것 같고.
숫자의 맨 뒷자리를 리스트 인덱스로 분류해서 계산하자.

어차피 숫자의 최대 길이는 100이니까 최대로 리스트를 만들어도 1000 밖에 되지 않는다.

바텀업 방식으로 모든 경우를 다 만든 다음에 마지막에 출력할 때 전체 행을 게산하도록 하자.

import sys

T = int(sys.stdin.readline())
dp = [[0] * 10 for _ in range(101)]

for i in range(10):
    dp[1][i] = 1

for x in range(2, 101):
    for y in range(10):
        up = y + 1
        down = y - 1
        if down >= 0:
            dp[x][down] += dp[x - 1][y]
        if up < 10:
            dp[x][up] += dp[x - 1][y]

res = 0
for i in range(10):
    res += dp[T][i]

print((res - dp[T][0]) % 1000000000)

경우만 신경 쓰지 말고. DP를 어떻게 구성할 지도 생각하면서 문제를 보자.