[SWEA] 종이 붙이기 (Python)

T = int(input())

for test_case in range(1, T + 1):
    n = int(input())
    dp = [1, 3]
    for i in range(2, n//10):
        dp.append(dp[i-1]+dp[i-2]*2)
    
    print('#{} {}'.format(test_case, dp[-1]))

전형적인 DP 문제이다.