[백준/파이썬] 10844번

📍백준 10844 문제

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

코드

import sys
input = sys.stdin.readline

# 뒷자리가 0,9이면 +1 , 1-8이면 +2


n = int(input())
arr = [[0]*10 for _ in range(n+1)]
for i in range(1, 10):
    arr[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            arr[i][j] = arr[i-1][1]
        elif 1 <= j <= 8:
            arr[i][j] = arr[i-1][j-1]+arr[i-1][j+1]
        else:
            arr[i][j] = arr[i-1][8]
print(sum(arr[n]) % 1000000000)

풀이

• 뒷자리가 0이거나 9이면 인접한 수가 1개밖에 없다. (0의 경우 1, 9의 경우 8)
• 뒷자리가 1~8인경우 인접한 수가 2개있다.(k인 경우, k-1 k+1)

그래서 길이가 i이고 k값인 경우, i-1길이의 값에서 [i-1][k-1] + [i-1][k+1]을 가지고 오면 된다.