[알고리즘/baekjoon] 11659_2×n 타일링 2(python)

문제

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

11727번: 2×n 타일링 2

# 11726번인 2*n 타일링에서 2*2 타일이 추가된 문제이다.

# 규칙을 찾기 위해서 예를 들어서 찾아본다.

# 예시

# n = 1 (|) -> 1

# n = 2 (||, =, ㅁ) -> 3

# n = 3 (|||, |=, =|, ㅁ|, |ㅁ) -> 5

# n = 4 (||||, =||, |=|, ||=, ==, =ㅁ, ㅁ=, ㅁㅁ, ㅁ||, |ㅁ|, ||ㅁ) -> 11

# 여기서 보면 n의 경우의 수에 n-1번째 경우의 수들이 1번씩 쓰이고, n-2번째 경우의 수들은 2번씩 쓰인다. 이것을 점화식으로 표현해보면 dp[i] = dp[i-1] + dp[i-2] * 2

import sys

N = int(sys.stdin.readline())
dp = [0 for _ in range(N+1)]

if N == 1:
  dp[1] = 1
  print(dp[N])
elif N == 2:
  dp[1] = 1
  dp[2] = 3
  print(dp[N])
else: # 본격적으로 n이 3부터 점화식이 적용
  dp[1] = 1
  dp[2] = 3
  for i in range(3,N+1):
    dp[i] = dp[i-1] + dp[i-2] * 2
  print(dp[N]%10007)