[백준 알고리즘/Python] 10844 쉬운 계단 수

문제

 

 

문제 이해

0을 제외한 모든 숫자는 앞에 올 수 있다.

이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1).

하지만 9 뒤엔 오직 숫자 8만이 올 수 있다.

 

dp테이블은 이차원 리스트이며 dp[자리 수][앞에 오는 숫자]=경우의 수입니다.

 

앞에 오는 숫자 = 0 )

dp[자리 수][0] = dp[자리 수 - 1][1]

※ dp[1][0] = 0이기 때문에 어차피 결과엔 영향을 미치지 않는다.

ex) 0, 01, 012 -> 안 셈!

 

앞에 오는 숫자 = 1~8 ) 

dp[자리 수][앞에 오는 숫자] = dp[자리 수 - 1][앞에 오는 숫자 -1] + dp[자리 수 - 1][앞에 오는 숫자 + 1]

dp[n][i] = dp[n][i-1] + dp

 

앞에 오는 숫자 =9 )

dp[자리 수][9] = dp[자리 수 - 1][8]

 

2차원 배열은 길이가 N일 때 맨 뒤에 숫자가 0~9가 몇개가 있는지 파악하는 것입니다.

 

ex)

b[2][2]는 2의 길이를 가지며 2로 끝나는 수의 가지수 입니다. 12,32가 있으니 2가 들어갑니다.

b[2][1]은 1로 끝나는 수가 1개밖에 없으니 1이 들어갑니다.

 

b[3][1]은 3의 길이를 가지며 1로 끝나는 수의 가지수 입니다. b[2][0]뒤에 1을 더한 개수, b[2][2]뒤에 1을 뺀 개수를 더하면 되겠죠.

b[2][0] + b[2][2] 가 됩니다.왜냐하면

b[2][0] = 10 -> 101이 되야하고 b[2][2] = 12 -> 121, 32 -> 321 이 되야하니 총 3개의 경우를 가지게 됩니다.

 

 

 

 

코드

import sys

num=int(sys.stdin.readline())

d = [[0] * 10 for _ in range(101)]

d[1]=[0,1,1,1,1,1,1,1,1,1]

for i in range(2,101):
    for j in range(10):
        if(j == 0):
            d[i][j] = d[i-1][j+1] % 1000000000
        elif(j == 9):
            d[i][j] = d[i-1][j-1] % 1000000000
        else:
            d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) % 1000000000


print((sum(d[num])) % 1000000000)