백준(BaekJoon) 11727번 : 2xn 타일링 2 - python 풀이

❓11727번 : 2xn 타일링 2

📈 문제 요약

2xn 직사각형을 1x2, 2x1, 2x2타일로 채우는 방법의 수를 구하면 되는 문제

🤨 접근법

2x 타일링 문제와 정확히 같은 유형의 dp 문제이다.

점화식을 유도하기 위해서 2x(n-1), 2x(n-2), … 직사각형으로 2xn 직사각형을 만드는 경우의 수를 생각해보면, 다음과 같이 2x(n-1)로 2xn 직사각형을 만들기 위해서는 오른쪽에 2x1 직사각형 하나를 덧붙이는 방법 밖에 없다.

다음 2x(n-2)로 2xn 직사각형을 만드는 경우를 생각해보면 다음과 같이 두 개의 2x1 직사각형을 붙이는 방법과 2x2 직사각형 하나를 붙이는 방법이 있다.

이 부분에서 헷갈릴만한 점은 2x(n-2) 직사각형에서 1x2 직사각형 2개를 덧붙일 수 있는 경우의 수를 고려하지 않는 점인데, 이 경우는 2x(n-1) 직사각형에서 2xn 직사각형을 만드는 경우의 수에 포함되어있는 방법이므로 여기에서 포함해버리면 전체적으로 봤을 때 중복이 발생한다. 즉, 아래 두 경우는 같은 경우의 수이다.

자 그러면 2x(n-3), 2x(n-4), …에서 2xn을 만들 수 있는 경우의 수는 모두 2x(n-1), 2x(n-2)에서 만들 수 있는 경우의 수이므로 고려하지 않아도 됨을 알 수 있다.

그러므로 유도할 수 있는 점화식은

$f(n) = 2f(n-2) + f(n-1)$이 된다.

2x(n-1)에서 2xn을 만드는 방법이 1가지, 2x(n-2)에서 2xn을 만드는 방법이 2가지 존재하기 때문이다.

이를 검증하기 위해서 아래와 같이 n=3 까지 경우의 수를 나열해보았다.

2x3 직사각형을 만들기 위해서 2x2 직사각형을 만드는 각 경우에 2x1 직사각형 하나를 붙였고, 2x1을 만드는 경우에 각각 2x2 직사각형 하나와 1x2 직사각형 2개를 붙여 만들어낼 수 있다. 이 방법으로 모든 크기의 직사각형을 채우는 경우의 수를 구할 수 있다.

🔡 코드

import sys

input = sys.stdin.readline

def tabulation(n):
    if dp[n] > 0:
        return dp[n]
    else:
        dp[n] = 2 * tabulation(n-2) + tabulation(n-1)
        return dp[n]

n = int(input())

dp = [0, 1, 3] + [0 for _ in range(2, n+1)] if n > 2 else [0, 1, 3]
print(tabulation(n)%10007)

점화식을 알았으므로 기저에 해당하는 dp[1]과 dp[2]를 바탕으로 tabulation을 진행하는 코드이다. dp[n]의 값이 존재하는 경우 그대로 반환하고, 존재하지 않으면 점화식을 바탕으로 dp[n]을 구해내어 저장 후 반환하는 방식이다.

입력 n이 1, 2가 들어오는 경우를 방지해서 dp배열을 선언하였다.