쉬운 계단 수 실버1 (백준, DP)

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):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 

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

 

풀이

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]