[백준 - Python] 10844. 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

코드

N = int(input())

dp = [[0] * 10 for _ in range(N)]

dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for n in range(1, N):
    dp[n][0] = dp[n-1][1]  # 끝에서 두 번째 수가 1이어야, 마지막 자리수가 0일 수 있음
    dp[n][9] = dp[n-1][8]  # 끝에서 두 번째 수가 8이어야, 마지막 자리수가 9일 수 있음

    for k in range(1, 9):
        dp[n][k] = dp[n-1][k+1] + dp[n-1][k-1]

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

 

0을 제외한 모든 숫자는 맨 앞에 나올 수 있고

1~8은 뒤에 올 수 있는 숫자가 +1 -1로 2종류이다.

하지만 9 뒤에는 8만 올 수 있다.

 

dp 테이블 dp[N][K]에는 N자리수의 K로 끝나는 수의 계단 갯수를 저장한다. 

 

한 자리 숫자인 경우에는 앞에 오는 수가 없음으로

인덱스를 0을 제외한 나머지 인덱스를 1로 초기화 해준다.

 

앞에오는 수가 1~8일 때에는

dp[자리수][K] = dp[자리수-1][K-1] + dp[자리수-1][K+1]이다 

 

예외인 경우는 0으로 끝나는 수와 9로 끝나는 수인데,

0으로 끝나는 경우는 끝에서 두번째 숫자가 1이어야만 함으로 a[N][0]=a[N−1][1]

9로 끝나는 경우는 끝에서 두 번쨰 숫자가 8이어야만 함으로 a[N][9]=a[N−1][8]이다.