[Python] BOJ 10844 - 쉬운 계단 수

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

10844번: 쉬운 계단 수

# 제목은 쉬운 계단수 이지만, 쉽지 않다.. (계단 수 문제가 더 쉬운듯)

# 그냥 단순 DP문제이다!

 

N = int(input())
# dp[i][j] = i자리수 중에서 j로 끝나는 수의 갯수
# dp[1]은 한자리수이므로 0,1,1,1,1,1,1,1,1이다.
dp = [[0] * 10 for _ in range(N+1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, N+1):
    for j in range(10):
        # i자리수 중 0으로 끝나는 수는 i-1자리수에서 1로 끝나는 수에 0을 붙인 수이다.
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        # 마찬가지로 9로 끝나는 수는 i-1자리수에서 8로 끝나는 수에 9를 붙인 케이스이다.
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        # 나머지는 i-1자리수 j-1로 끝나는 수와 j+1로 끝나는 수에 j를 붙인 케이스이다.
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

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

(solved.ac 티어: 실버 1)

 

# 시험기간이라 ps를 못했는데, 시험끝났으니 다시 열심히 해보자!