백준 14852 - 타일 채우기 3

문제 링크 : https://www.acmicpc.net/problem/14852

 

문제

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

입력

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

출력

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

풀이 과정

# 14852. 타일 채우기 3 ( GOLD 4 )

import sys
input = sys.stdin.readline

# 2xN 크기의 벽을 2x1, 1x2, 1x1
# ## #. #.
# .. #. ..

# 2x1을 채우는 방법 (x2)
# A A
# B A

# 2x2를 채우는 방법
# i-1 (x2)
# #A #A
# #B #A
# i-2 (x3)
# AA AA BC 
# BB BC AA

# 번외로, 1x2 를 사용해 끊지 못하고 한 덩어리를 만들 수 있음
# i 마다 2개
# CAA AABBC
# BBD DEEFF
#
# AAC CAAEE
# DBB BBDDF
#
# i-3 부터 1 까지 2개씩 곱
# i-3 x 2 + i-4 x 2 ... -> (i-3 + i-4 ...) x 2 -> 누적합

n = int(input().rstrip())
dp = [0 for _ in range(n+1)]
dp_sum = [0 for _ in range(n+1)]
for i in range(1, n+1):
  if i == 1: 
    dp[i] = 2
    dp_sum[i] = 2
  elif i == 2: 
    dp[i] = 7
    dp_sum[i] = dp_sum[i-1] + 7
  elif i == 3: 
    dp[i] = 22
    dp_sum[i] = dp_sum[i-1] + 22
  else: 
    dp[i] = (dp[i-1] * 2 + dp[i-2] * 3)
    dp[i] = (dp_sum[i-3] * 2 + 2 + dp[i])
    dp_sum[i] = (dp_sum[i-1] + dp[i]) % 1000000007
    dp[i] %= 1000000007

print(dp[n])