1. 문제

10844번

2. 코드

• 이 문제는 2차원 메모이제이션 공간을 활용한 동적계획법 문제이다.
• bottom-up 방식으로 풀 수 있으며,
• 메모이제이션 공간 내 요소들의 관계(점화식)와 초기값 설정이 중요!

n = int(input())
mod = 1000000000 # 답을 1,000,000,000 으로 나눈 나머지 값 출력

'''
이 문제에서는 몇번째 숫자인지 나타내기 위한 공간과
0~9까지 어떤 숫자인지 나타내기 위한 공간 2개가 필요하다.
'''
dp = [[0]*10 for _ in range(n+1)] # 메모이제이션 공간 초기화

# 문제를 풀다가 발견한 것인데 아래와 같은 표현에서는 제대로 연산이 안된다.
# 이유는 좀 더 연구가 필요하다.
# dp = [[0] * 10] * ( n + 1 ) 

'''
dp[i]는 총 10개 원소의 배열인데 각 0 ~ 9까지 숫자를 의미
dp[1], 즉 첫번째 숫자에서 0이 맨 앞에 올 수 없으므로 dp[1][0] = 0
따라서, dp[1]은 아래와 같이 초기화 한다.
'''
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n+1):
    dp[i][0] = dp[i - 1][1]
    # i번째 자리에 0이 올 때, 앞자리에는 1만 올 수 있다.
    for j in range(1, 9):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
        # i번째 자리에 숫자 j(1이상 8 이하)이 올 때,
        # 앞자리에는 j-1, j+1 올 수 있다.
    dp[i][9] = dp[i - 1][8]
    # i번째 자리에 9가 올 때, 앞자리에는 8만 올 수 있다.
print(sum(dp[n]) % mod)