2xn 타일링 2 [백준 11727] - python

import sys
input = sys.stdin.readline
mod_num = 10_007

def BOJ11727() :
  n = int(input())
  dp = [0 for _ in range(1001)]
  dp[1] = 1
  dp[2] = 3
  for i in range(3, 1001) :
    dp[i] = ((dp[i-2] * 2) % mod_num + (dp[i-1]) % mod_num) % mod_num
  
  print(dp[n])

BOJ11727()

 

접근 방법 

 

1.  3번째 인덱스부터 도형을 그리려면 n-1 번째에서는 [2x1] 타일밖에 이용을 할 수가 없다.

n-2 번째에서는 [1x2] 두개, [2x2] 하나를 이용하는 방법 두개씩 가능하다

이를 점화식으로 나타내면 

dp[n] = dp[n-2] * 2 + dp[n-1]  이 된다.

나머지 연산만 분배법칙에 따라 적용해주면 된다.

 

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

11727번: 2×n 타일링 2