[백준] 10844번 : 쉬운 계단 수 (python 파이썬)

 

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

10844번: 쉬운 계단 수

 

 

 

문제 정리 : 계단 수는 인접한 모든 자리의 차가 1인 수이다. 입력 값 N자리의 계단 수의 계수를 출력한다.

import sys
 
mod = 10**9 ## 십억
N=int(sys.stdin.readline())
mm=[[0]*10 for i in range(N+2)] ## 1-N의 자리까지의 수, 10은 각자리의 일의 자리 수

mm[1]=[0,1,1,1,1,1,1,1,1,1] ## N == 1인 경우

for i in range(2,N+1):
    mm[i][0] = mm[i-1][1] ## 일의 자리가 0인 경우
    mm[i][9] = mm[i-1][8] ## 일의 자리가 9인 경우

    for j in range(1,9):
        mm[i][j] = mm[i-1][j-1] + mm[i-1][j+1] ## 나머지 경우
    
   

print(sum(mm[N])%mod) ## 정답 출력

하나씩 따지기에는 개수가 너무 많으므로 일의 자리수를 기준으로 하여 차원을 더한다.

만약 이전 경우가 계단 수 였다면, 이번의 계단 수는 이전 계단 수의 일의 자리에서 1을 더하고 뺀 값을 1의 자리로 가질 것이다.

따라서 N = 1인 경우를 미리 만들어 놓고, dp 형식으로 계속 더해가는 형식을 통해 값을 구할 수 있다.

 

하지만 일의 자리가 0인 경우와 9인 경우는 특이점을 가진다.

0인 경우와 9인 경우는 1을 빼하고 더한 값이 서로 공유하기 때문에 수가 겹치는 문제가 발생할 수 있다. 0은 전에 1인 값에서 -1한 값으로 하고, 9는 전에 8인 값에서 +1 한 것으로 함으로서 이를 해결  수 있다.