[Python] 백준 10844반: 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1

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

print(sum(dp[N]) % 1000000000)

bfs 같은 것을 통해 직접 구현하는 것은 터무니없이 느리다. 따라서 DP를 이용한다.

dp[length][digit]의 의미는, 길이가 length이면서 마지막 자릿수가 digit일 때의 경우의 수이다.

첫째자리가 0이 올 수는 없다고 명시되어 있으므로, dp[1]은 0111111111이다.

이후에 위 사진처럼 dp를 가져다오면 되는 것이다.

여기서 주의할 점은, dp[i][0]과 dp[i][9]이다. 0으로 끝나는 계단숫자는 오로지 '~10'뿐이며, 9로 끝나는 계단숫자는 '~89'뿐이기 때문이다.

 

다음은 N이 5일 때의 dp이다.