[테스트케이스 추가] 백준 10844 번: 쉬운 계산 수 python, 파이썬

1. 문제

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

10844번: 쉬운 계단 수

 

 

 

2. 풀이

마지막 숫자가 무엇인지에 대한 정보도 필요해서 차원을 하나 늘려 기록해야한다.

마지막 숫자가 0이면 1로 증가시키는 방법밖에 없고 마지막 숫자가 9이면 8로 줄이는 방법 밖에 없다.

 

 

 

3. 구현

import sys
# sys.stdin=open('input.txt')
from collections import deque
mod = 10**9

N=int(sys.stdin.readline())
mm=[[0]*10 for _ in range(N+2)]
mm[1]=[0,1,1,1,1,1,1,1,1,1]

for i in range(2,N+1):
    mm[i][0] = mm[i-1][1]
    mm[i][9] = mm[i-1][8]
    for j in range(1,9):
        mm[i][j] = mm[i-1][j-1]+mm[i-1][j+1]

# print(mm)
print(sum(mm[N])%mod)

 

 

 

 

4. 테스트케이스 추가

 

3

답: 32

 

4

답: 61

 

5

답: 116