[LeetCode] 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 10^9 + 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 shown above.
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 1000
n*2 배열과 같이 타일을 배치할 수 있는 공간이 주어지고,
도미노 모양(1*2)과 트로미노 모양(ㄴ자)의 타일을 이용해 주어진 공간을 몇 가지의 방법으로 배치할 수 있는지 세는 문제.
무조건 공간을 빽빽하게 다 채워야 하고, 타일 종류 및 숫자의 제한은 없다.
그리고 문제에 제시된 modulo 10^9 + 7 이라는 건,
n이 커짐에 따라 타일을 놓는 방법이 기하급수적으로 커지는데, 처리 가능한 정수 범위를 초과할 수도 있다.
이를 방지하기 위해 결과값을 10^9 + 7(=1,000,000,007)으로 나눈 나머지를 리턴하라는 뜻이다.
이게 Medium 문제라고???? 문제 난이도는 뭘 기준으로 하는걸까?ㅋㅋㅋ
var numTilings = function(n) {
/*
* ㄴ모양은 n이 3*i일 때부터 2*i개씩 사용할 수 있다.
* n = 3 -> ㄴ*2 / ㅡ*3
* n = 4 -> ㄴ*2 & ㅡ*1 / ㅡ*4
* n = 6 -> ㄴ*4 / ㄴ*2 & ㅡ*3 / ㅡ*6
*/
let modulo = Math.pow(10,9) + 7;
let dp = new Array(n+1).fill(0);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(let i=3; i<n+1; i++){
dp[i] = (2*dp[i-1] + dp[i-3]) % modulo;
}
return dp[n]
};
우선 ㄴ모양은 n이 3의 배수가 되면, 한 쌍씩 사용할 수 있게 된다. 홀수로 사용할 수는 없다.
다시 말해서... n이 3*i 일 때마다 i*2개씩 사용할 수 있는 것이다.
dp[n] 을 2*n의 타일을 채우는 수라고 했을 때,
dp[0]은 아무 타일도 안 넣기로 1이고, dp[1] = 1, dp[2] = 2 처럼 진행된다.
이 때, dp[i] 를 구한다고 생각해 보자.
dp[i-1]의 마지막 한 줄을 채우고 싶을 때는 도미노를 1개 세워서 놓는 방식이 추가된다.
dp[i-2]의 마지막 두 줄을 채우고 싶으면 도미노를 눕혀서 2개 놓는 방식이 추가된다.
그리고 끝에 ㄴ자 트로미노를 놓는 경우를 생각해 보면,
트로미노는 3칸씩 차지하게 되고, 트로미노가 회전하는 경우를 생각해서
3칸이 남은 때에는 dp[i-3] * 2가 추가된다.
즉, 점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] * 2 + ... 인데.
3개 이상이 남는 경우에는 ㄴ과 ㄱ자 모양을 활용해서 대칭이 가능해지므로,
dp[i] = dp[i-1] + dp[i-2] + 2 * (dp[i-3] + dp[i-4] + ... + dp[0]) 이 된다.
이걸 정리를 해 보면...
dp[i] = dp[i-1] + dp[i-2] + 2*(dp[i-3] + ... + dp[0])
dp[i-1] = dp[i-2] + dp[i-3] + 2*(dp[i-4] + ... + dp[0])
=> dp[i] - dp[i-1] = dp[i-1] + dp[i-3]
=> dp[i] = 2 * dp[i-1] + dp[i-3] 이 된다!!!
그냥 그걸 구현하기만 하면 된다...
이해하려니 너무 어렵다...
걍 n에 대한 값을 구한 다음에 규칙 찾아서 푸는 게 더 편하긴 할듯ㅠㅠㅋㅋㅋ
