leetcode 790) Domino and Tromino Tiling

LV. Medium 🧐

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

Domino and Tromino Tiling - LeetCode

문제

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

문제 해결법

n = 4라고 생각해보자. 2 * 4로 만들 수 있는 조합은 아래와 같다.

1. n = 3일 때 만든 조합 뒤에 domino (1 * 2)를 붙이는 방법

2. n = 2일 때 만든 조합 뒤에 domino (2 * 1)를 두 개 붙이는 방법

3. n = 1일 때 만든 조합 뒤에 trominole를 붙일 수 있는 방법 2개

4. n = 0일 때 만든 조합 뒤에 trominole과 dominole를 조합해서 붙일 수 있는 방법 2개

 

💡 점화식

dp[n] = dp[n - 1] + dp[n - 2] + 2 * (dp[n - 3] + dp[n - 4] ... + dp[0])
      = dp[n - 1] + dp[n - 3] + dp[n - 2] + dp[n - 3] + 2 * (dp[n - 4] + ... dp[0])
      = dp[n - 1] + dp[n - 3] + dp[n - 1]
      = 2 * dp[n - 1] + dp[n - 3]

 

답이 큰 값이 나와 1e9 + 7로 나눈 나머지를 리턴하라고 하는데 그 이유가 궁금하다면 아래 링크 클릭!

https://developer-eun-diary.tistory.com/19

문제에서 왜 항상 1e9+7로 나눈 나머지를 구하라고 할까?(모듈러 연산)

 

해결 코드

#include <iostream>
#include <vector>

using namespace std;

// two tromino must need 2 * 3
// two domino(1 * 2) must need 2 * 2

class Solution {
public:
	int numTilings(int n) {
		vector<long> dp;
		int mod = 1e9 + 7;

		if (n < 3)
			return n;
		dp.assign(n + 1, 0);
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 5;
		for (int i = 4; i <= n; ++i) {
			dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
		}
		return dp[n];
	}
};

int main() {
	Solution sol;

	cout << sol.numTilings(3) << endl;
}

 

비슷한 문제 추천(백준)

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링