[백준/Python3] 10844 쉬운 계단 수

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

---

풀이

길이가 N이며, 인접한 수의 차이가 모두 1인 모든 수의 개수를 구하는 문제다. 이때 90,09는 계단수가 아니다.

Dynamic Programming 문제다. 2차원 dp table을 이용해서 해결할 수 있다. dp[i]가 N의 길이인 계단수의 개수다. 이때 dp[i][j]는 다음과 같다.

dp[i][j] => i의 길이를 가지며 숫자 j로 끝나는 계단 수의 개수

끝자리 수는 1 차이가 나야 계단수라 할 수 있으므로 n의 길이를 가지며 끝 숫자가 j인 계단수인 숫자는 아래와 같은 식으로 표현할 수 있다.

dp[n][j] = dp[n-1][j-1] + dp[n-1][j+1]

단, 끝자리가 0 또는 9일 때는 서로가 인접해도 계단수가 아니므로 이 경우를 따로 제외해야한다. 최종적으로 다음과 같이 나타낼 수 있다.

if j==0:
	dp[n][j] = dp[n-1][j+1]
elif j==9:
	dp[n][j] = dp[n-1][j-1]
else:
	dp[n][j] = dp[n-1][j-1] + dp[n-1][j+1]

1,000,000,000으로 나누지 않으면 숫자가 너무 커져 메모리 초과가 일어날 수 있으니 매번 처리를 해줘야한다.

코드

# Initial
N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N+1)]
answer = 0
mod = 1000000000

# Make DP table
for i in range(1, 10):
    dp[1][i] = 1
if N > 1: 
    for i in range(2, N+1):
        for j in range(0, 10):
            if j == 0:
                dp[i][j] = dp[i-1][j+1] % mod
            elif j == 9:
                dp[i][j] = dp[i-1][j-1] % mod
            else:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod
        

# Answer
for i in range(10):
    answer = (answer + dp[N][i]) % mod
print(answer)