BOJ 11726 - 2 x n 타일링

 

DP란 무엇인가... 답을 알고 보는데도 한참 걸렸던 문제다. 패턴을 손으로 하나하나 그려가면서 경우의 수가 피보나치 수열과 동일하게 증가한다는 걸 알게 됐는데, 항상 그렇게 된다는 걸 증명하지 못해서 3시간은 시간을 더 쓴 것 같다. 결국 답에 도달하고 보니 이렇게 간단했나... 싶어서 허망했다만, 결국 대부분의 DP문제가 그런 것 같기도 하다. 여하튼 문제를 보면

 

 

\( 2 \times n \) 타일을 채워야하기 때문에 \( 2 \times 1 \) 타일은 하나로도 칸을 채워갈 수 있지만, \( 1 \times 2 \) 타일은 위 아래로 두개를 붙여야만 칸을 채울 수 있다. 결국 타일을 채울 수 있는 도형은 위의 세 도형 뿐이다. 필자는 이걸 넓이 1과 2로 순열을 만들어서 풀려고 했었는데 대차게 실패했었다.

 

 

2n타일의 한단계 전을 생각해보자. 위에서 분류한 사용할 수 있는 도형은 3가지다. 이 도형들을 붙여서 n에 도달하는 경우, 즉 n-1 혹은 n-2에서 n으로 오는 방법을 생각해볼 수 있다. 그러면 위 그림처럼 3가지 경우가 나온다. 이때 \( 2 \times 1 \) 하나를 붙인 경우와 2개를 연달아 붙인 경우는 중복이다. 2단계 전에서 \( 2 \times 1 \) 을 하나 붙인 경우에서 다시 하나 더 붙인 경우와 완전히 동일한 모양이기 때문이다.

 

따라서  n의 길이를 만드는 경우의 수는 n-1길이를 만드는 방법과 n-2를 만드는 방법을 1번씩 합친 것과 같다. 점화식은 아래와 같다.

 

\( f(n) = f(n-1) + f(n-2) \)

 

위에서 경우의 수가 피보나치 수열과 같다고 했던 이유가 나온다. 점화식이 완전히 동일하다. 이제는 구현만 하면 된다. 아래는 파이썬 코드

 

# BOJ 11726 2xn 타일링
# 넓이가 1인 도형과 2인 도형으로 n의 넓이를 채우는 문제와 같다
# 넓이가 3인 도형을 만드는 경우의 수 1 1 1, 1 2 , 2 1
# 문제를 작게 나눠보면
# -> 넓이가 2인 도형에서 1을 더하는 경우
# -> 넓이가 1인 도형에서 2를 더하는 경우
# 따라서 3을 만드는 경우의 수는 1에서 2 더하기, 2에서 1더하기의 경우를 합친 것과 같다. 도형의 넓이가 2개뿐이기 때문에 다른 경우의 수는 없음
# 1에서 2를 더하는 경우 = 1 + (1+1), 1 + 2
# 2에서 1을 더하는 경우 = 2 + 1
#   -> 여기서 1+2를 하지 않는 이유는, n-2항에서 이미 구해지기 때문이다.
#   -> 즉, 값이 왼쪽에 추가되는 경우는 고려할 필요가 없다.
# a(n) = a(n-2) + a(n-1) -> 피보나치

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline
MOD = 10007


def get_input():
    return int(input())


def solution(n):

    dp = [0 for _ in range(n + 2)]
    # 1,2의 값은 결정되어있음
    dp[1] = 1
    dp[2] = 2

    def fibonacci(n):
        if dp[n] == 0:
            dp[n] = (fibonacci(n - 1) + fibonacci(n - 2)) % MOD
        return dp[n]

    return fibonacci(n)


if __name__ == "__main__":
    print(solution(get_input()))