[백준][Python] 14945 불장난

dp[층수][둘사이 거리]의 경우의 수로 계산.

거리가 그대로일 경우 둘(아래아래, 대각,대각)

거리가 줄경우 하나(대각아래)

거리가 늘경우 하나(아래대각)

거리가 0인경우는 그냥 배제

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0]*(n+1) for _ in range(n+1)]
dp[2][1] = 2
for i in range(3,n+1):
    for j in range(1,i):
        dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-1] + dp[i-1][j+1])%10007
sum_n = 0
for i in range(1,n):
    sum_n += dp[n][i]
print(sum_n%10007)