[LeetCode 75] Medium - 790. Domino and Tromino Tiling

문제

790. Domino and Tromino Tiling

 

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

 

Example 1:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 1000

 

문제 설명 (GPT)

이 문제는 2 x n 크기의 보드를 도미노(2x1)와 트로미노(ㄱ 모양) 타일을 이용해서 채우는 방법의 수를 계산하는 문제입니다. 단, 결과가 매우 커질 수 있으므로 109+710^9 + 7109+7로 나눈 나머지를 반환해야 합니다.

 

재귀와 메모이제이션을 사용하여 2×n2 \times n2×n 보드를 도미노와 트로미노로 덮는 경우의 수를 계산합니다.

 

문제 이해

이 문제는 2×n2 \times n2×n 크기의 보드를 도미노(2x1)와 트로미노(ㄱ 모양) 타일을 사용하여 덮는 방법의 수를 계산하는 것입니다.

• 도미노: 세로로 2×12 \times 12×1 또는 가로로 1×21 \times 21×2의 공간을 덮습니다.
• 트로미노: 2×32 \times 32×3의 공간 중 3칸만 덮는 타일로, 여러 방향으로 회전 가능합니다.

조건:

• 모든 칸은 완전히 덮어야 합니다.
• 타일은 겹치거나 보드 밖으로 나가면 안 됩니다.

결과:

• 보드를 덮는 가능한 방법의 수를 계산한 후, 결과를 109+710^9 + 7109+7로 나눈 나머지를 반환합니다.

---

풀이 접근

이 문제는 **동적 프로그래밍(DP)**을 사용하여 해결합니다.

• 보드 크기가 커질수록 가능한 타일 배치 조합이 늘어나기 때문에, 이전 크기에서의 결과를 이용해 현재 크기의 경우를 계산할 수 있습니다.
• **"짝수 상태"와 "홀수 상태"**로 나누어 문제를 세분화하고 재귀적으로 계산합니다.

정의:

1. 짝수 상태 (even):
   • 2×n 보드를 완전히 덮는 경우를 계산합니다.
2. 홀수 상태 (odd):
   • 2×n 보드를 덮은 뒤, 1칸이 튀어나온 상태의 경우를 계산합니다.

아이디어:

• 짝수 상태는 기본 상태로, 모든 칸이 덮인 완전한 상태입니다.
• 홀수 상태는 트로미노 타일 일부가 덮여 "비대칭적" 상태를 만들어내는 것을 처리하기 위해 도입되었습니다.
• 두 상태가 서로 재귀적으로 호출되며, 결과를 계산합니다.

 

점화식

짝수 상태 (even)

짝수 상태를 계산하기 위한 점화식은 다음과 같습니다: even(n) = even(n−1) + even(n−2) + 2⋅odd(n−2)

1. even(n−1): 마지막 칸을 도미노로 세로로 채운 경우.
2. even(n−2): 마지막 두 칸을 도미노로 가로로 채운 경우.
3. 2⋅odd(n−2): 마지막 세 칸을 트로미노로 덮은 경우 (두 방향 포함).

홀수 상태 (odd)

홀수 상태를 계산하기 위한 점화식은 다음과 같습니다: odd(n) = even(n−1) + odd(n−1)

1. even(n−1): 트로미노를 사용하여 마지막 칸을 홀수 상태로 만든 경우.
2. odd(n−1): 기존 홀수 상태에서 도미노를 추가로 덮은 경우.

 

초기값

초기값은 작은 n에 대해 계산된 값입니다:

1. even(0) = 1: 2×0 크기의 보드를 덮는 경우는 "아무것도 하지 않는 것" 한 가지입니다.
2. even(1) = 1: 2×1 보드는 도미노 한 개로 덮을 수 있는 한 가지 방법만 존재합니다.
3. odd(0) = 0: 2×0 보드에서는 홀수 상태가 불가능합니다.

 

복잡도 분석

 

• 시간 복잡도:
  • 메모이제이션을 통해 각 n에 대해 한 번만 계산하므로 O(n)입니다.
• 공간 복잡도:
  • 캐시 배열과 재귀 호출 스택으로 인해 O(n)의 공간이 필요합니다.

 

예제 실행복잡도 분석 

n=4:

1. even(4) = even(3) + even(2) + 2⋅odd(2)
2. 계산:
   • even(3) = 5, even(2) = 2, odd(2) = 2
   • even(4)=5+2+4 = 11

n=5:

1. even(5) = even(4) + even(3) + 2⋅odd(3)
2. 계산:
   • even(4) = 11, even(3) = 5, odd(3) = 4
   • even(5) = 11+5+8 = 24

 

 

추가 정보

왜? 짝수 상태 (even) 에서 2⋅odd(n−2) 수행?

 

핵심 아이디어: 2⋅odd(n−2)란?

1. 짝수 상태 even(n) 정의

짝수 상태 even(n)은 2×n 보드를 완전히 덮는 경우의 수를 의미합니다.

2. 트로미노의 기여

트로미노는 2×3 크기의 영역을 덮습니다. 따라서 트로미노를 사용할 경우, 보드의 마지막 세 칸에 영향을 미칩니다.

3. 2⋅odd(n−2)의 의미

트로미노를 보드의 마지막 세 칸에 배치하면, 보드의 나머지 부분(2×(n−2))은 홀수 상태 odd(n−2) 로 남습니다.

• 트로미노는 2×3의 공간을 덮으며, 회전 가능성이 있기 때문에 두 가지 방향으로 배치할 수 있습니다:
  1. 트로미노가 오른쪽 위로 "ㄱ" 형태.
  2. 트로미노가 오른쪽 아래로 "ㄴ" 형태.

따라서, 각각의 트로미노 방향에 대해 odd(n−2) 경우의 수만큼 새로운 타일링 방법이 생깁니다.
결론적으로 2⋅odd(n−2)는 이 두 가지 방향에서 만들어지는 모든 가능한 경우의 수를 더한 것입니다.

---

2⋅odd(n−2) 시각적 이해

예: n=4

• 현재 보드 크기는 2×4.
• 트로미노를 마지막 세 칸 (n=4에서 오른쪽 끝) 부분에 배치한다고 가정합니다.

---

왜 "짝수 상태에서 홀수 상태로 연결"이 중요한가?

트로미노는 "짝수 상태"를 "홀수 상태"로 변환하는 역할을 합니다.

• 트로미노는 2×3 공간을 덮으면서 남은 공간을 홀수 상태로 만들고, 남은 부분을 다시 odd(n−2)를 기반으로 계산해야 합니다.

이런 이유로, 짝수 상태 even(n) 계산에는 홀수 상태 odd(n−2)가 포함됩니다.

 

홀수 상태 이해~

 

Code (GPT)

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10 ** 9 + 7  # 결과가 매우 커질 수 있으므로 나머지 연산을 적용할 값

        # 캐시 배열 생성: "even" 상태에 대한 메모이제이션
        hasEvenCashe = [False] * (n + 1)  # 이미 계산한 "even" 상태인지 여부를 저장
        evenCashe = [None] * (n + 1)  # "even" 상태에 대한 결과를 저장

        # "even" 상태 계산 함수: 2xN 보드를 완전히 덮는 경우의 수
        def even(N):
            if N == 0:  # 2x0 보드는 완전히 비어 있는 상태로, 경우의 수는 1가지
                return 1

            if hasEvenCashe[N]:  # 이미 계산된 값이 있으면 캐시에서 반환
                return evenCashe[N]

            count = 0  # 경우의 수를 저장할 변수
            count += even(N - 1)  # 마지막 칸을 도미노로 세로로 채운 경우
            if N - 2 >= 0:
                count += even(N - 2)  # 마지막 두 칸을 도미노로 가로로 채운 경우
                count += 2 * odd(N - 2)  # 마지막 세 칸에 트로미노를 사용한 경우

            hasEvenCashe[N] = True  # 현재 상태를 계산했음을 표시
            evenCashe[N] = count % MOD  # 결과를 캐시에 저장하며 MOD 연산 적용
            return evenCashe[N]

        # 캐시 배열 생성: "odd" 상태에 대한 메모이제이션
        hasOddCashe = [False] * (n + 1)  # 이미 계산한 "odd" 상태인지 여부를 저장
        oddCashe = [None] * (n + 1)  # "odd" 상태에 대한 결과를 저장

        # "odd" 상태 계산 함수: 2xN 보드에서 1개의 타일이 튀어나온 상태의 경우의 수
        def odd(N):
            if N == 0:  # 2x0 보드는 "odd" 상태가 불가능하므로 경우의 수는 0
                return 0

            if hasOddCashe[N]:  # 이미 계산된 값이 있으면 캐시에서 반환
                return oddCashe[N]

            count = 0  # 경우의 수를 저장할 변수
            count += even(N - 1)  # 마지막 칸을 트로미노로 덮어 "odd" 상태로 만든 경우
            count += odd(N - 1)  # 기존 "odd" 상태에서 도미노를 추가한 경우

            hasOddCashe[N] = True  # 현재 상태를 계산했음을 표시
            oddCashe[N] = count % MOD  # 결과를 캐시에 저장하며 MOD 연산 적용
            return oddCashe[N]

        return even(n) % MOD  # 최종적으로 "even(n)"의 값을 반환

 

참고 문제 풀이

https://youtu.be/fQd104LDSfU?si=bLbxck9-0-E3wU0q

 

https://youtu.be/o75alNvYqHU?si=hXTX84BB-Z69n-8E

 

============================================================================================

https://artofcom77.tistory.com/218

[DP-1D][Medium] 790. Domino and Tromino Tiling

 

직관적으로.. => RecursionError: maximum recursion depth exceeded in comparison

class Solution:
    def numTilings(self, n: int) -> int:        
        def dfs(n):
            if n==1:
                return 1
            elif n==2:
                return 2
            elif n==3:
                return 5
            
            mod = 10**9 + 7
            sub_sum = 0

            # 올바르게 nn에 대해 dfs 호출
            for nn in range(n - 3, -1, -1):
                sub_sum = (sub_sum + dfs(nn)) % mod

            # 전체 결과 계산
            prev = dfs(n-1)
            prevprev = dfs(n-2)
            res = (prev + prevprev + (sub_sum * 2) + 2) % mod
            return res

        return dfs(n)

메모리제이션 => RecursionError: maximum recursion depth exceeded in comparison

class Solution:
    def numTilings(self, n: int) -> int:  
        memo = {}      
        def dfs(n):
            if n==1:
                return 1
            elif n==2:
                return 2
            elif n==3:
                return 5

            if n in memo:
                return memo[n]
            
            mod = 10**9 + 7
            sub_sum = 0

            # 올바르게 nn에 대해 dfs 호출
            for nn in range(n - 3, -1, -1):
                sub_sum = (sub_sum + dfs(nn)) % mod

            # 전체 결과 계산
            prev = dfs(n-1)
            prevprev = dfs(n-2)
            res = (prev + prevprev + (sub_sum * 2) + 2) % mod
            memo[n] = res
            
            return memo[n]

        return dfs(n)

DP로..

class Solution:
    def numTilings(self, n: int) -> int:          
        if n==1:
            return 1
        elif n==2:
            return 2
        elif n==3:
            return 5

        dp = [0]*(n+1)

        dp[1] = 1
        dp[2] = 2
        dp[3] = 5
        
        mod = 10**9 + 7
        sub_sum = 0

        # 올바르게 nn에 대해 dfs 호출
        # for nn in range(n - 3, -1, -1):
        for nn in range(4, n+1):
            sub_sum = (sub_sum + dp[nn]) % mod

        # 전체 결과 계산
        for i in range(4, n+1):
            dp[i] = (dp[i - 1] + dp[i - 2] + 2 * sum(dp[:i - 2]) + 2) % mod
        return dp[n]

추가 문제들

1. 873. Length of Longest Fibonacci Subsequence
2. 688. Knight Probability in Chessboard
3. 42. Trapping Rain Water