백준 10844번 "쉬운 계단수"

문제

백준 10844번 쉬운 계단수

풀이

n(자릿수)가 1일 경우, 0을 제외한 모든 숫자(0으로 시작하는 수는 없다고 적혀있다)가 맨 뒷자리에 있을 경우는 각 1이다.

n이 2일 경우 맨뒷자리가 0일 때 경우는 10, 1이 오는 경우는 21,
2가 오는 경우는 12, 21이다.

이렇게 진행하다보면 DP를 써야만 할 것 같은 표를 얻을 수 있다.

위 표를 보면 특정 위치의 숫자는 해당 위치의 대각선 위 숫자의 합인 것을 알 수 있다.
(0과 9의 경우 대각선 위 숫자가 하나이므로 그대로 내려오는 것을 알 수 있다.)

규칙도 알았으니 코드작성 ㄱㄱ

Python 코드

import sys

input = sys.stdin.readline

n = int(input())
arr=[[0 for i in range(10)] for j in range(n+1)]

# n = 1일 경우 맨 뒷자리에 1~9가 올 경우의 수 1로 채우기
for i in range(1,10):
  arr[1][i]=1

# n = 2부터 
for i in range(2,n+1):
  for j in range(10):
    if j == 0:
      arr[i][j] = arr[i-1][j+1]
    elif j == 9:
      arr[i][j] = arr[i-1][j-1]
    else:
      arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]


print(sum(arr[n])%1000000000)