[Python]10844. 쉬운 계단 수

 

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

10844번: 쉬운 계단 수

---

 

계단이라는 특성으로 인해서 문자열 비교 없이 DP를 이용해서 풀 수 있다.

단, 2차원 DP를 이용하는 것이 편리하다.

DP[2]를 구하기 위해 DP[1]을 참조 하는 모습 도식화

점화식으로 풀어보면 다음과 같다.

DP[i][0] = DP[i-1][1]

DP[i][1] = DP[i-1][0] + DP[i-1][2]

DP[i][2] = DP[i-1][1] + DP[i-1][3]

...

DP[i][8] = DP[i-1][7] + DP[i-1][9]

DP[i][9] = DP[i-1][8]

 

DP[1]을 미리 초기화하여 별도의 예외처리를 하지 않는다.

MAX = 100
MOD = 1000000000
DP = [[0]*(10) for _ in range(MAX+1)]
 
DP[1] = [0,1,1,1,1,1,1,1,1,1]
 
for i in range(2, MAX+1):
    DP[i][0] = DP[i - 1][1] % MOD
    DP[i][9] = DP[i - 1][8] % MOD
    for j in range(1,8+1):
        DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % MOD
 
x = int(input())
print(sum(DP[x])% MOD)