백준 11727번: 2×n 타일링 2 (파이썬)

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

11727번: 2×n 타일링 2

 

문제

 

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

입력

 

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

 

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

풀이

 

백준 11726번: 2×n 타일링 문제에서 조금 변형된 버전이다. 이 문제 역시 DP로 해결할 수 있다.

이전 문제에서 2×2 타일이 추가되었다. 이 문제에서도 1×2, 2×1, 2×2 크기의 직사각형을 사용하기 때문에 n=1, 2에 대해서는 직접 구해 초기화를 해야 한다. n=1일 때는 2×1 크기의 직사각형 하나를 사용하는 방법 밖에 없다. n=2일 때는 2×1 크기의 직사각형을 두 개 사용하는 방법과 1×2 크기의 직사각형을 두 개 사용하는 방법, 2×2 크기의 직사각형을 하나 사용하는 방법 세 가지로 나뉜다. k >= 3에 대해서는 n=k-1일 때의 방법에서 가장 오른쪽에 2×1 크기의 직사각형 하나를 더 채워 넣는 방법과 n=k-2일 때의 방법에서 가장 오른쪽에 1×2 크기의 직사각형을 두 개를 더 채워 넣는 방법과 2×2 크기의 직사각형 하나를 채워 넣는 방법이 추가된다. 따라서 본 문제의 점화식은 arr[i] = arr[i-2] + arr[i-2] + arr[i-1] (단, i >= 3)이다. 

 

 

소스 코드

import sys

n = int(sys.stdin.readline())

arr = [0, 1, 3]

for i in range(3, n+1):
  arr.append(arr[i-2] + arr[i-2] + arr[i-1])

print(arr[n]%10007)