n = int(input()) dp = [0] * (n+1) dp[0], dp[1] = 1, 1 for i in range(2, n+1): dp[i] = dp[i-1] + 2*dp[i-2] print(dp[n]%10007)
다음 점화식을 이용하여 해결한다. dp[i] = dp[i-1] + 2*dp[i-2]