난이도

Gold 4

문제

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

1

예제 출력

2

해설

타일 채우기 문제는 DP에서 아주 흔한 문제 형태이다. 그러나 의외로 난항을 겪게 되었는데 그 이유는 1x1타일의 존재 때문이다. 처음에는 생각하지 못했는데 1x1타일 때문에 2x3, 2x4, 2x5 …에서 2개씩의 unique한 타일 형태가 계속 발생한다. 그랙서 dp를(메모이제이션) 위한 리스트가 총 두개가 필요했다.

제출 코드

n = int(input())
memo = [2, 7, 22]
memo2 = [2, 9, 31]
for i in range(3,n):
    s = sum([2*memo2[i-3], 3*memo[i-2], 2*memo[i-1]])
    s += 2
    memo.append(s%1000000007)
    memo2.append(memo2[-1]+memo[-1])
print(memo[n-1]%1000000007)