BOJ 11726: 2×n 타일링 - 파이썬(Python)

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

<접근 방법>

2 x n 타일로 만들 수 있는 모든 경우의 수를 구하는 문제이다.

 

우선, 가장 간단한 경우들을 살펴보자. n = 1일 때에는 1가지 경우만 가능하다. 

 

그렇다면 n = 2일 때에는 어떻게 구성될까? 해답은 아래의 2가지 경우가 가능하다.

n = 2일 때 가능한 모든 경우

 

 

이제 n = 3일 때에는 어떻게 구성될지 분석해보자. 우선, 가능한 모든 경우의 수는 아래의 그림과 같이 3가지이다.

 

n = 3일 때 가능한 모든 경우

 

위의 그림에서 규칙을 찾아보자. 2 x n 타일은 "가로로 2개" 또는 "세로로 1개"를 붙여서 구성할 수 있다는 것을 알 수 있다.

 

N = 1에 "가로 2개"타일을 붙인 경우(좌)와 N = 2에 "세로 1개"타일을 붙인 경우(우)의 모습

 

결과적으로, 아래의 식을 이용해서 문제를 해결할 수 있을 것이다. 

T[N] = T[N - 1] + T[N - 2]

<소스 코드>

위의 접근법을 이용하여 코드로 구현한 결과이다.

import sys

a = int(sys.stdin.readline())
tile = [0] * (a + 1)
for i in range(1, a + 1):
    if i == 1:
        tile[i] = 1
    elif i == 2:
        tile[i] = 2
    else:
        tile[i] = tile[i - 1] + tile[i - 2]

print(tile[a] % 10007)