[BOJ] 11726번: 2xn 타일링

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

 

문제

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

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

 

풀이

풀이 방법을 알아내는 데까지 거의 1시간이 걸렸따...

 

직사각형의 세로는 무조건 2이므로, 1x2 타일을 놓을 때에는 반드시 

1x2 타일 두개

이러한 모양이 된다. 하나의 2x1 타일을 사용할 경우, 직사각형을 채우기 위해서는 반드시 아래에 1x2 타일이 하나 더 사용되어야 하기 때문이다.

 

계속 고민하다 보니 이 문제는 결국 1과 2를 사용하여 n을 만드는 경우의 수!!!를 구하는 문제라는 것을 알게 되었다.

여기서의 1은 1x2 모양의 타일이고, 2는 2x1모양의 타일 2개(위 사진처럼)를 말한다.

 

1과 2로 2를 만드는 경우의 수는 1 + 1, 2로 2가지이고,

 

3 = 1 + 1 + 1 = 2 + 1 = 1 + 2 이며, 이때 1 + 1과 2는 2를 만드는 경우의 수이다.

즉 2를 만드는 경우의 수에다가 1을 더하는 경우 + 1을 만드는 경우의 수에 2를 더하는 경우인 것이다.

 

이해하기 어렵게 설명한 거 같은데, 쉽게 말하자면 1과 2를 이용하여 n을 만들 때, n-1에 1을 더하거나 / n-2에 2를 더하는 방법이 있다.

2x(n-1) 타일에 2x1 타일을 붙이거나 2x(n-2) 타일에 1x2 타일 두개를 붙임으로써 2xn 직사각형을 만들 수 있는 것이다.

즉 n-1의 경우 + n-2의 경우를 하면 된다!! (이걸 알아내는데 이렇게 오래 걸렸다니...😓)

 

n = int(input())
dp = [0] * (n + 1)

for i in range(1, n + 1):
    if i == 1:
        dp[i] = 1
    elif i == 2:
        dp[i] = 2
    else: 
        dp[i] = dp[i - 2] + dp[i - 1]
    
    dp[i] %= 10007
        
print(dp[n])

 

흡사 피보나치와 유사해보인다.

1과 2에 대해서는 각각 예외처리를 해주고,

나머지의 경우에는 i-2의 경우의 수와 i-1의 경우의 수를 더하면 된다.