[백준] 10844: 쉬운 계단 수 (Python)

문제📖

풀이🙏

• dp[자리수][맨 뒤에 올 수 있는 숫자] 를 통해 2차원 dp테이블을 정의한다.
  1) 1자리일 경우 0을 제외한 1~9까지 1가지가 존재한다.
  2) 2자리일 경우
  1. 맨 뒤에 0이 오는 경우: 10 (1가지)
  2. 맨 뒤에 1이 오는 경우: 21 (1가지)
  3. 맨 뒤에 2가 오는 경우: 12, 32 (2가지)
     즉, 이러한 규칙성을 보면 dp테이블의 왼쪽, 오른쪽 대각선 위에 테이블을 합친것과 같다.
     `dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
• 맨 뒤에 0이 오는 경우는 오른쪽 대각선 위만 존재하고,
  j == 0 -> dp[i][j] = dp[i-1][1]
• 맨 뒤에 9이 오는 경우는 왼쪽 대각선 위만 존재한다.
  j == 9 -> dp[i][j] = dp[i-1][8]

코드💻

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

for i in range(2, n+1): # i는 자리수
    for j in range(10):
        if j == 0: # 맨 뒤에 갈 수 있는 경우의 수가 0 일 경우
            # 왼쪽 대각선 위
            dp[i][j] = dp[i-1][1]
        elif j == 9: # 맨 뒤에 갈 수 있는 경우의 수가 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]) % 1000000000)