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)