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

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

11726번: 2×n 타일링

 

문제

 

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

 

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

 

출력

 

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

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

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

 

소스 코드

import sys

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

arr = [0, 1, 2]

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

print(arr[n]%10007)