[LeetCode] 790. Domino and Tromino Tiling, Medium

1. 문제

• 도미노 타일과 트리미노 타일이 주어질 때, 2xn 크기의 타일을 모두 덮을 수 있는 경우의 수를 구하라.
• 값이 큰 경우 10^9 + 7로 나눈 나머지 값을 반환하라.

2. 해결

function numTilings(n: number): number {
  const mod = 10 ** 9 + 7;
  const dp: number[] = [1, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
  }
  return dp[n];
};

• 일단 이 문제를 완벽하게 이해하지는 못했다.
• 마지막에 두는 타일의 경우의 수로 따져야 하는 것 까진 알겠는데, 점화식을 유도하는 과정이 벽이었다.

https://leetcode.com/problems/domino-and-tromino-tiling/solutions/116581/detail-and-explanation-of-o-n-solution-why-dp-n-2-d-n-1-dp-n-3/

• leetcode solution에 올라온 내용이다.
• 보면, dp[3]과 dp[4]의 점화식에서 dp[n] = dp[n-1] + dp[n-2] + 2*(dp[n-3]+ ... + dp[0]) 식을 뽑아낼 수 있다.
• 여기서 dp[n-3]을 더하기루 풀어쓰면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3] + dp[n-3] + 2 * (dp[n-4] + ... + dp[0])이라는 식이 나오고, dp[n-2] + dp[n-3] + 2 * (dp[n-4] + ... + dp[0]) 은 dp [n-1]에 대한 점화식이 된다.
• 결국 dp[n] = dp[n-1] + dp[n-1] +dp[n-3] = 2*dp[n-1] + dp[n-3]이라는 점화식을 뽑아낼 수 있다.