Baekjoon Training #10844

 

---

#10844 쉬운 계단 수

---

import sys
input = sys.stdin.readline

n = int(input())

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

# 1부터 9까지의 수로 첫번째 배열을 채움
for i in range(1,10):
    dp[1][i] = 1

# dp[n자리 수][n자리 숫자일 때 해당 index 앞에 올 수 있는 일의 자리 수]
# 2 자리수부터 시작
for i in range(2, n+1):
    for j in range(10): # index기반으로 전부 조사
        # 뒷자리가 0일 때는 이전에 한가지 경우의 합으로 구함
        if j == 0 : dp[i][j] = dp[i-1][j+1]
        # 뒷자리가 9일 때는 이전에 한가지 경우의 합으로 구함
        elif j == 9 : dp[i][j] = dp[i-1][j-1]
        # 뒷자리가 2~8일 때는 이전에 두가지 경우의 합으로 구함
        else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

# overflow를 막기 위해 문제에서 요구한대로 1000000000으로 나눈 나머지를 출력
print(sum(dp[n]) % 1000000000)

2차원 배열을 이용한다는 발상을 하는 것이 중요했다. dp[a][b]꼴로 초기화를 해두고 '[a]는 자리수, [b]는 마지막 자리의 값' 방식으로 2차원 배열을 만들고 값을 계속해서 더해나가는 방식으로 문제를 해결하였다.

---