백준 #14852 타일 채우기 3

코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline


n = int(input())
p = 10 ** 9 + 7
dp = [0] * (10 ** 6 + 1)
dp[0] = 1
dp[1] = 2
x = sum(dp[:2])
for i in range(2, n + 1):
    dp[i] = 2 * x + dp[i - 2]
    x += dp[i]

print(dp[n])

풀이

풀이는 그림으로!!

n = 3부터 생기는 지그재그타일 2개를 잘 체크해주고 시간초과가 걸리지 않게 prefix_sum을 구해 dp에 더해주는 방식으로 풀면된다

(위 그림의 마지막 줄에서 i = 1가 아닌 i = 0부터로 수정!)

\[\therefore a_{n}=2\sum_{i=0}^{n-1}a_i+a_{n-2}\]