10844번 Python

이 문제는 개인적으로 좀 어려웠는데 이해할 때까지 보면서 대충 감을 잡을 수 있었다.

 

123, 1234 와 같은 1이 인접한 계단의 수를 구하는 것이다. 이게 왜 DP 알고리즘이 적용되지라고 생각했는데 그 이유를 알 수 있었다. 마지막에 4가 온다고 가정해보자. 4에 인접한 수는 3과 5가 있다. 즉, 34와 54를 일단 둘 수 있고 3에서는 2와 4가 인접하다. 그래서 234 434가 될 수 있다.

 

이런 식으로 내려가다보면 결국 4자리 수일 때, 마지막에 있는 숫자 4를 기준으로 3으로 끝나는 계단의 수 + 5로 끝내는 계단의 수를 더하면 4자리의 마지막인 계단의 수를 구할 수 있는 것이다.

 

물론 예외도 있다. 마지막 수가 1이나 9는 인접하는 수가 2와 8밖에 없다. 0으로는 시작할 수 없기 때문이다.

 

# 2자리이고 마지막 자리에 있는 수가 2이면
_2 -> _에 들어가는 수는 1이나 3 = 1자리이고 마지막이 1인 수 + 1자리이고 마지막이 3인 수

# 점화식
d[2][2] = d[1][1] + d[1][3]
d[i][j] = d[i-1][j-1] + d[i-1][j+1]

# 2자리이고 마지막 자리에 있는 수가 0이면
_1 -> _에 들어가는 수는 1

# 점화식
d[2][0] = d[1][1]
d[i][j] = d[i-1][1]

# 2자리이고 마지막 자리에 있는 수가 9면
_9 -> _에 들어가는 수는 8
d[2][9] = d[1][8]
d[i][j] = d[i-1][8]

이렇게 점화식을 구할 수 있고 코드로 구성하면 다음과 같다.

 

import sys

MOD = 1000000000
n = int(sys.stdin.readline())
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] % MOD
        elif j == 9: dp[i][j] = dp[i - 1][8] % MOD
        else: dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD

print(sum(dp[n]) % MOD)