LeetCode - 790. Domino and Tromino Tiling

문제링크

 

문제 설명

너비가 n, 높이가 2인 보드가 주어집니다. 이 보드를 다음 두 종류의 타일로 채우려 합니다:

1. 도미노 타일 (2×1)
2. 트로미노 타일 (L자 모양의 3칸) – 회전 가능

모든 칸은 타일로 정확히 한 번씩 덮여야 하며,
두 타일링이 서로 다르다고 간주되는 경우는 다음과 같습니다:

서로 상하좌우로 인접한 두 칸이 있을 때, 한 타일링에서는 하나의 타일이 두 칸 모두를 덮고 있지만,
다른 타일링에서는 그렇지 않은 경우

정수 n이 주어질 때,
2 × n 보드를 타일링하는 서로 다른 방법의 수를 구하세요.
단, 정답이 매우 클 수 있으므로 10⁹ + 7로 나눈 나머지를 반환하세요.

제한 사항

• 1 <= n <= 1000

예시

Example 1:

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

 

Example 2:

Input: n = 1
Output: 1

풀이 흐름

• 백준의 2xn 타일링 문제와 비슷한 것 같습니다.
• 맨 마지막에 올 수 있는 타일의 종류는 다음과 같습니다.

• 탑 다운 방식으로 구현했습니다.

코드

class Solution {
    int MOD = 1000000007;
    int[] dp;

    public int numTilings(int n) {
        dp = new int[n + 1];
        dp[0] = 1;
        return f(n);
    }

    private int f(int n) {
        if (n < 0) {
            return 0;
        }
        if (dp[n] != 0) return dp[n];
        dp[n] = ((f(n - 1) % MOD) + (f(n - 2) % MOD)) % MOD;
        for (int i = n - 4; i >= 0; i -= 2) {
            dp[n] = (dp[n] + (f(i) * 2) % MOD) % MOD;
        }
        for (int i = n - 3; i >= 0; i -= 2) {
            dp[n] = (dp[n] + (f(i) * 2) % MOD) % MOD;
        }
        return dp[n] % MOD;
    }
}