백준 10844 쉬운 계단 수 - python

출처 : 

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

10844번: 쉬운 계단 수

풀이 :

n = int(input())

dp = [[0] * 10 for i in range(n+1)]

for i in range(1,10):
    dp[1][i] = 1

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

문제의 제목과 그렇지 못한 난이도인거 같다.

사실 문제가 어렵기보단 이런 유형의 익숙해져야 할 것 같다.

 

다이나믹 프로그래밍을 이용해야 하는 문제인데 자릿수의 끝이 0과 9일때는 1~8 까지와는 다르게 만들수 있는 수가 적다는 것을 캐치했는데 피보나치를 생각해서 틀렸다.

 

이 문제는 문제에서 제공하는 N 만큼의 [0~9] 까지의 2차원을 만들어줘야한다.

예를 들어 N=3 이라면 [0,0,0,0,0,0,0,0,0,0] [0,0,0,0,0,0,0,0,0,0] [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0]   이렇게 만들어준다. 

 

그 다음 0 앞에 올수 있는 숫자는 1 밖에 없고 9 앞에 올 수 있는 숫자는 8 뿐이므로 다음 0과 1의 자리의 수는 이전 행의 1과 9를 이용한다.

 

그리고 나머지의 경우는 4로 예를 들면 4는 3과 5가 앞에 올수 있으므로 이전행의 3의 경우의수와 5의 경우의 수를 더해주면 된다.

설명보다 코드를 읽는 것이 더 빨리 이해 될 것이라 생각한다.