1. 문제

---

출처: 백준 10844번 쉬운 계단 수

2. 풀이

---

계단수를 만드는 방법을 숫자의 길이가 1일 때부터 생각해 보자.

숫자의 길이가 1이라면, 1~9까지 9개의 숫자가 가능하다.

다음 길이가 2일 때는, 1~8까지의 숫자에 하나씩 차이 나는 경우를 붙이는 것을 생각해 볼 수 있다.

Ex) 01, 21 , ... , 78, 98

길이가 2일 때는 01이 불가능한 경우이긴 하지만, 길이가 3일 때부터는 가능한 경우가 생기니 예시로 적어보았다. (101과 같은 경우가 가능해진다.)

그리고 숫자가 0이나 9의 경우에는 하나씩만 붙일 수 있다.

Ex) 10, 89

즉, 계단 수의 숫자를 계산하는 방법은
끝의 자릿수가 1~8일 때는 각 끝자리 수의 앞뒤 숫자로 끝나던 계단 수의 개수를 더해주면 된다.
그리고 끝의 자릿수가 0과 9라면 각 끝자리수가 1과 8로 끝나는 계단 수의 개수를 가져오면 된다.

최종적으로 입력 길이에 맞는 계단 수의 숫자를 모두 더해주고, 주어진 숫자로 나눈 나머지를 출력한다.

3. 소스코드

---

n = int(input())

dp = [[0]*10 for _ in range(n+1)]
for i in range(1,10):
    dp[1][i] = 1

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

4. 그 외

---