[Python] 백준 11726 2xn 타일링

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

 

문제 분석

• 2xn 크기의 직사각형을 2x1, 1x2 타일로 채우는 방법의 수 % 10007 출력

 

풀이

완탐 - 시간초과

• n을 1과 2의 합이 되는 중복순열의 수 (순서o, 중복o)
• 조합 : product

dp

• 이전에 계산한 것들을 저장
• dp[i] = 2 x i 크기의 타일에 들어갈 경우의 수
• dp[1] : 1가지 [1]
• dp[2] : 2가지 [(1,1), 2]
• dp[3] : 3가지 [(1,1,1), (1,2), (2,1)]
• dp[4] : 5가지 [(1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)]
  
  
  
• I가 짝수이면 이전에 대해 +1
• i가 홀수이면 이전에 대해 +2

 

정답 코드

1. 시간초과 : 완탐

import sys
input = sys.stdin.readline
from itertools import product

n = int(input())
arr = [1,2]
cnt = 0

for i in range(n+1) :
    for j in product(arr, repeat=i) :
        if sum(list(j)) == n :
            cnt += 1

print(cnt)

 

2. dp - 점화식

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(n+1)]
if n >= 1 :
    dp[1] = 1
if n >= 2 :
    dp[2] = 2
if n >= 3 :
    for i in range(3, n+1) :
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)