문제

• 백준-14852 : 타일 채우기 3
• 문제링크

풀이

이 문제의 경우에는 길이 3 이상을 채우려고 할 때 특이 케이스가 매번 발생한다는 점을 주의해야 한다.

leng = int(input())

memo = [0]*(leng+1)
memo[0:3] = [1, 2, 7]

summemo = 0
for i in range(3, leng+1):
    summemo += memo[i-3]
    memo[i] = (2*memo[i-1] + 3*memo[i-2] + 2*summemo)%1000000007

print(memo[leng])