파이썬으로 1×2 도미노 타일로 3×n 블록을 채우는 방법의 수 구하기

문제 설명

숫자 n이 주어졌을 때, 1 x 2 크기의 도미노 타일을 사용하여 3 x n 크기의 직사각형 블록을 빈틈없이 채우는 방법의 수를 구하는 프로그램을 작성해 보겠습니다. 도미노는 필요에 따라 가로 또는 세로로 회전하여 배치할 수 있습니다. 만약 답이 매우 커진다면 10^9 + 7로 나눈 나머지를 반환하면 됩니다.

예를 들어 입력이 n = 4라면, 가능한 배치 방법은 총 11가지이므로 출력은 11이 됩니다.

해결 전략

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• n이 홀수인 경우: 3 x n 영역의 전체 칸 수가 홀수 개가 되는데, 각 도미노는 정확히 2칸을 차지하므로 어떻게 배치하더라도 영역을 완전히 채울 수 없습니다. 따라서 0을 반환합니다.
• n이 짝수인 경우: 두 가지 상태를 추적합니다.
  • cs(complete state): 현재 위치까지 영역을 완전히 채운 경우의 수
  • os(odd state): 한 칸이 비어 있는 불완전한 상태의 경우의 수

두 상태 사이의 점화식은 다음과 같습니다.

• cs = 3 × cs + os
• os = 2 × cs + os

알고리즘 단계

1. m = 10^9 + 7로 설정합니다.
2. n이 홀수이면 0을 반환합니다.
3. cs = 1, os = 0으로 초기화합니다.
4. i를 2부터 n까지 2씩 증가시키며 반복합니다:
   • cs = 3 * cs + os
   • os = 2 * cs + os
5. cs mod m을 반환합니다.

예제 코드 (Python)

다음 구현을 통해 더 잘 이해해 보겠습니다.

class Solution:
    def solve(self, n):
        m = (10 ** 9 + 7)
        if n % 2 == 1:
            return 0
        cs = 1
        os = 0
        for i in range(2, n + 1, 2):
            cs, os = (3 * cs + os, 2 * cs + os,)
        return cs % m

ob = Solution()
n = 4
print(ob.solve(n))

입력

4

출력

11

복잡도 분석

시간 복잡도: O(n) — n/2번의 반복만 수행하면 됩니다.
공간 복잡도: O(1) — 두 개의 변수만 사용하므로 추가 메모리가 거의 필요하지 않습니다.