[BOJ] 10844번 - 쉬운 계단 수

---

문제설명

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

10844번: 쉬운 계단 수

사고과정

• 1,2,3 더하기 5 유형과 비슷한 유형이였다. 이것도 2차원 리스트를 DP 테이블로 하는 것이었다. 이 때, DP 테이블에서 행($i$)는 글자 길이인 N을 의미하고 열($j$)는 맨 뒷자리에 나올 수 있는 숫자인 0부터 9까지이다.
• DP 테이블을 2차원으로 그리고 N = 3일 때까지 경우의 수를 세서 해보면 규칙을 파악할 수 있다. 바로 왼쪽 대각선 위와 오른쪽 대각선 위의 합이 DP[i][j] 값이라는 것! 이 때 j = 0 일 때는 왼쪽 대각선 위가 없으므로 오른쪽 대각선 위만 더하고 j = 9 일때는 오른쪽 대각선 위가 없으므로 왼쪽 대각선 위만 계산한다.
• 구글링해서 핵심 아이디어만 보고 소스코드로 구현하는 데는 오래걸리지 않았다.. 이코테에서 풀어본 금광이랑 비슷한 유형이라 못 풀어서 아쉬웠다.. 경우의 수를 나열하고 패턴을 찾는 게 가장 관건인 것 같다.. 눈치가 빠르면 DP 유형인 걸 눈치 채고 N =2 일때만 나열하고 패턴 포착할 수도 있을 듯 하다. 이래서 문제를 많이 풀어야 할 듯 싶다.

풀이(스스로 못 푼 풀이)

n = int(input())
dp = [[0] * 10 for _ in range(n)]
mod = int(1e9)
# 초기값 DP 테이블에 넣기
for j in range(1, 10):
    dp[0][j] = 1

for i in range(1, n):
    for j in range(0, 10):
        if j == 0:
            left_up = 0
        else:
            left_up = dp[i-1][j-1]
        if j == 9:
            right_up = 0
        else:
            right_up = dp[i-1][j+1]
        dp[i][j] = left_up + right_up

print(sum(dp[n-1]) % mod