백준 11727 2xn 타일링 2

과정

• 2xn 타일링 문제와 다르게, 2x2 타일이 추가되었다.

• 다이나믹 프로그래밍

  • 점화식 세우기

• dp[i] = dp[i-1] + 2 * dp[i-2]

• 추가되는 타일은 왼쪽에 붙는다고 생각해보면, dp[i-1]에서 1 길어지는 경우 (빨강), dp[i-2]에서 2 길어지는 경우 (파랑)을 고려하면 된다.

  • 2짜리 타일을 채울 때, 2x1로만 채우는 경우는 dp[i-1]에서 고려되므로 1x2, 2x2인 경우만 고려하기 위해서 dp[i-2]에 2를 곱한다.

• 길이가 3인 경우의 수
  

• 길이가 4인 경우의 수
  

N = int(input())
lst = [0] * (N+1)
if N == 1:
    print(1)
    exit()
elif N == 2:
    print(3)
    exit()
lst[1] = 1
lst[2] = 3
for i in range(3, N+1):
    lst[i] = lst[i-1] + lst[i-2] * 2
ans = lst[-1]
if ans > 10007:
    print(ans % 10007)
else:
    print(ans)

• 길이가 1, 2 인 경우 예외 처리를 하지 않으면 인덱스 에러 발생하므로 주의