LeetCode 790. Domino and Tromino Tiling

 

 

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

Domino and Tromino Tiling - LeetCode

 무슨 문제인지 보아하니, DP를 사용하는 문제 같다. 백준의 2xn 타일링에서 조금 더 꼬아 놓은 듯 하다.

 

먼저 2xn타일링 문제를 간단히 살펴보자.

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

11726번: 2×n 타일링

이 문제는 DP를 사용하는데, 이전 차수의 타일 상태에서 값을 가져와 푼다.

위의 그림에서 차수는 N이 된다. N=1인 경우와 N=2인 경우에는 상태가 고정이 되어 있다. N=3인 경우를 보면 색상이 다르게 칠해져 있다. 

검은색 블록을 보았을 때, 4개가 모자란 경우와 2개가 모자란 경우로 나누어서 계산을 한다. 즉 이전 상태에서 블록을 추가해서 현재 상태를 완성할 수 있는 조건을 찾는다! N=2일 경우의 수에서 맨 왼쪽에 블록 1개만 추가하는 경우와 N=1일 경우에 블록 2개를 붙이는 경우의 수가 있을 것이다. 이를 중복되지 않게 처리하게 되면 dp(n) = dp(n-1) + dp(n-2)의 점화식이 나오게 되고, O(n)의 시간으로 풀 수가 있다.

 

하지만 지금 문제에서는 경우의 수를 약간 꼬아 놨다. 그래서 블록의 모양을 보고 경우의 수를 나누어 주어야 한다. 이전 상태를 불러올 수 있게 하는 것이 중요하다.

결과적으로 나올 수 있는 경우의 수는 3가지가 있고, 이전 상태에 대해서는 위와 같은 경우의 수를 모두 더하면 직사각형이 될 수 있다. 여기서 알 수 있는 것은, 2번과 3번의 경우의 수는 항상 같다! 왜냐하면 대칭의 모양을 하고 있고, 실제로 계산을 해 보면 같은 수가 나온다. 그래서 계산을 줄여서 3xn 배열이 아닌 2xn 배열로 선언해서 풀이가 가능하다. 초기값만 잘 지정해 두면 나머지는 O(n)으로 풀이가 가능하다.

var numTilings = function (n) {
  const MOD = 10 ** 9 + 7;
  if (n <= 2) {
    return n;
  }

  const answer = Array.from({ length: n + 1 }, () => Array(2).fill(0));
  answer[1][0] = 1;
  answer[2][0] = answer[2][1] = 2;
  for (let i = 3; i <= n; i++) {
    answer[i][0] =
      (answer[i - 1][0] + answer[i - 2][0] + answer[i - 1][1]) % MOD;
    answer[i][1] = (2 * answer[i - 2][0] + answer[i - 1][1]) % MOD;
  }
  return answer[n][0];
};