790. Domino and Tromino Tiling

[zeikar]

Problem link

https://leetcode.com/problems/domino-and-tromino-tiling/

Problem Summary

2 * n 칸을 도미노와 트로미노 타일로 채울 수 있는 경우의 수를 구하는 문제.

Solution

전형적인 타일링 DP 문제. 1차원으로 되는 것 같은데 더 직관적인 2차원 배열로 풀었다.

dp[i][0]: i 번째 칸까지 딱 채울 수 있는 경우의 수
dp[i][1]: i-1번째 칸은 다 채웠지만 i 번째 칸은 1칸만 채운 경우의 수

그림으로 나타내면

이런 느낌이다.

그렇다면 점화식을 세울 수 있는데
dp[i][0] = dp[i - 2][0] + dp[i - 1][0] + dp[i - 1][1]
dp[i][1] = dp[i - 2][0] * 2 + dp[i - 1][1]

간단하게 설명해보면
dp[i][0] 에서

• dp[i - 2][0]: 2칸 이전 뒤에 = 모양으로 2개 붙이는 것
• dp[i - 1][0]: 1칸 이전 뒤에 | 1개 붙이는 것
• dp[i - 1][1]: 1칸 이전 뒤에 ㄱ 혹은 ㄴ 모양을 붙이는 것

dp[i][1] 에서

• dp[i - 2][0]: 2칸 이전 뒤에 ㄱ 혹은 ㄴ 모양을 붙이는 것 (2가지 이므로 2를 곱함)
• dp[i - 1][1]: 1칸 이전 뒤에 - 1개를 붙이는 것

1e9+7로 mod 연산하는 것만 붙여서 for문으로 돌려주면 된다.

Source Code

class Solution:
    def numTilings(self, n: int) -> int:
        dp = [[0] * 2 for _ in range(n + 1)]
        dp[0][0] = 1
        dp[1][0] = 1

        for i in range(2, n + 1):
            dp[i][0] = (dp[i - 2][0] + dp[i - 1][0] + dp[i - 1][1]) % int(1e9 + 7)
            dp[i][1] = (dp[i - 2][0] * 2 + dp[i - 1][1]) % int(1e9 + 7)

        return dp[n][0]