[백준 11727번] 2 x n 타일링 2 - python

문제 링크

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

풀이 

- dp 문제 

- dp[i] 는 2*i 크기의 직사각형을 채우는 방법의 수 

dp[i-2]에서 1*2 두개나 2*2 를 놓을 수 있으므로 2 * dp[i-2] 

이 때 2*1 두개를 놓는 방법은 dp[i-1]에서 2*1 하나 놓을 때와 겹치므로 고려하지 않는다.

dp[i-1]에서 2*1 하나 놓을 수 있으므로 dp[i-1] 

따라서 dp[i] = 2*dp[i-2] + dp[i-1] 

import sys
input= sys.stdin.readline

n = int(input())

if n == 1:
  print(n)
elif n == 2:
  print(3)
else:
  dp = [0] * n
  
  dp[0] = 1
  dp[1] = 3

  for i in range(2,n):
    dp[i] = dp[i-1] + 2*dp[i-2]

  print(dp[n-1]%10007)