BAEKJOON #11726) 2xn 타일링 | DP | Python

11726번: 2×n 타일링

0️⃣ 초기화

이 문제를 풀기 위해서는 2x1 타일링 방법 개수와 2x2 타일링 방법 개수를 초기화하고 시작합니다.

2x1을 타일링하는 방법은 아래의 방법으로 1개 입니다.

2x2를 타일링하는 방법은 아래 방법으로 2개 입니다.

 

1️⃣ 2x3 타일 생각해보기

초기화 한 후, 2x3 타일링은 2x1타일링에 1x2타일 2개를 붙이고, 2x2타일링에 2x1타일 1개를 붙이면 됩니다.

 

2️⃣ 2x4 타일 생각해보기

2x4 타일 또한 앞의 방법처럼 2x2 타일에 1x2 타일 2개를 붙이고, 2x3타일에 2x1 타일 1개를 붙이면됩니다.

 

3️⃣ 점화식 세우기

위의 두개의 예시를 통해 우리는 패턴 즉, 점화식을 세울 수 있습니다.

2xn 타일링 방법은 2x(n-2)타일에 1x2 타일 2개를 붙이고, 2x(n-1)타일에 2x1 타일 1개를 붙이면됩니다.

즉, $f(n) = f(n-2) + f(n-1)$ 이라는 점화식을 도출할 수 있습니다.

1x2 타일 2개

2x1 타일 1개

4️⃣ 코드 작성

문제의 입출력 조건에 맞추어 위의 과정을 코드로 작성하면 다음과 같습니다.

import sys
input = sys.stdin.readline

def tile(n):
	dp = [0] * 1001
	dp[1] = 1
	dp[2] = 2

	for idx in range(3, n+1):
		dp[idx] = dp[idx - 1] + dp[idx - 2]
	return dp[n]

if __name__ == '__main__':
	n = int(input())
	print(tile(n) % 10007)