백준 10844(쉬운 계단 수) - Python(파이썬) - DP

10844번: 쉬운 계단 수

예제 풀이

일단 첨에 보고 이해가 안되었다. 문제 뜻은 이와 같다 계단 같은 경우에는 무조건 +1 , -1 차이가 난다는 것이다. 

 자릿수가 1인 수를 구하라고 하면 1 - 9 이렇게 9개가 존재한다라는 의미이다.

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1

 자릿수가 2인 수를 구하라고 하면 

  0 _ -> 1개(1) , 1 _ -> 2개(0,2) , 2 _ -> 2개(1,3) , 3 _ -> 2개(2,4) , 4 _ -> 2개(3,5) ,

  5 _ ->2개(4,6) , 6 _ -> 2개(5,7) , 7 _ -> 2개(6,8) , 8 _ -> 2개(7,9) , 9 _ ->1개(8) 

0	1	2	3	4	5	6	7	8	9
dp[0+1] =1	dp[1-1] +dp[1+1] =2	dp[2-1] +dp[2+1] =2	dp[3-1] +dp[3+1] =2	dp[4-1] +dp[4+1] =2	dp[5-1] +dp[5+1] =2	dp[6-1] +dp[6+1] =2	dp[7-1] +dp[7+1] =2	dp[8-1] +dp[8+1] =2	dp[9-1] =1

dp의 합을 더한 후에 dp[0]의 값을 제외시킨다.

 

 

💻Python(파이썬)

import sys
n = int(sys.stdin.readline())
dp = [1]*10
array = []
for i in range(n-1):
    array = [0]*10
    for j in range(10):
    	#1~9
        if j>0:
            array[j]+=(dp[j-1]%1000000000)
        #0~8
        if j<9:
            array[j]+=(dp[j+1]%1000000000)
    #계산한 array 값을 dp에 킵
    dp = array.copy()

print((sum(dp)- dp[0])%1000000000)