[백준 10844번] 쉬운 계단 수

# 1 2 3 4 5 6 7 8 9

# [1]0, [1]2, [2]1, [2]3, [3]2, [3]4, [4]3, [4]5, [5]4, [5]6, [6]5, [6]7, [7]6, [7]8, [8]7, [8]9, [9]8

# [10]1, [12]1, [12]3, [21]0, [21]2, [23]2, [23]4, [32]1, [32]3, [34]3, [34]5, [43]2, [43]5

n = int(input())

dp = [[0]*10 for i in range(101)]

for i in range(1,10):
    dp[0][i] = 1

for i in range(n):
    for j in range(10):
        if j == 0:
            dp[i+1][j+1] += dp[i][j]
        elif j == 9:
            dp[i+1][j-1] += dp[i][j]
        else:
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j-1] += dp[i][j]

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

이번 문제는 길이가 N인 인접한 모든 자리의 차이가 1인 계단 수의 개수를 구하는 문제였다.

 

처음에 이 문제를 접근할 때는 마지막 자리의 수에 따라 모든 경우의 수를 리스트에 저장하여 풀었었는데, 메모리초과나 시간초과가 발생하여 다른 방식으로 풀이하기로 하였다.

 

그래서 모든 경우의 수를 구하게 되면 시간복잡도 O(n^2)로 풀이하게 되기 때문에 별도의 자료구조에 작은 문제의 값을 저장하면서 풀이하는 DP 알고리즘을 사용하기로 하였고, 수의 자리가 늘어날 때마다 자리수를 모두 구하는 것이 아니라 마지막 자리 수의 개수에 초점을 맞추어 문제를 풀이하였다.

 

DP 문제를 풀 때마다 느끼는 것이지만 생각한 풀이가 잘 풀리지 않거나 시간(메모리)초과가 발생하면, 작은 문제의 답부터 천천히 구해가면서 점화식을 도출하거나 패턴을 파악하는 것이 가장 중요한 것 같다 :)