[프로그래머스] 3 x n 타일링

문제

3 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12902

 

 

풀이

설명

길이가 n인 직사각형을 채우는 방법의 수를 구하는 문제입니다.

 

DP를 이용해 해결할 수 있습니다.
dp[n]은 길이가 n인 직사각형을 채우는 방법의 수입니다.

 

직사각형의 길이가 짝수일 때, 각 길이에 맞는 전용 블록을 만들 수 있습니다.

 

만들 수 있는 전용 블록의 종류는 다음과 같습니다.
n = 2일 때, 3가지
n = 4 이상의 짝수일 때, 2가지

 

아래는 그 예시입니다.

직사각형의 길이가 n일 때, 만들 수 있는 전용 블록 예시

 

따라서 dp[n] = dp[n - 2]에 길이가 2인 전용 블록을 채우는 가짓수 + dp[n - x]에 길이가 x인 전용 블록을 채우는 가짓수입니다. (x는 4이상의 짝수)

 

단, dp[0]은 아무것도 채우지 않는 경우로 1입니다.

 

이름 점화식으로 나타내면 다음과 같습니다.

점화식

 

예시 코드

function solution(n) {
  // n이 홀수일 경우, 블록 채우기 불가
  if (n % 2 === 1) return 0;

  const LIMIT = 5000;
  const MOD = 1000000007;
  const dp = Array(LIMIT + 1).fill(0);
  dp[0] = 1;
  dp[2] = 3;

  // 2칸 전용 블록을 만드는 방법은 3가지, 남은 부분은 (n - 2) * 3이므로 dp[n - 2] * 3
  // x가 4이상의 짝수일 경우, x칸 전용 블록을 만드는 방법은 2가지, 남은 부분은 (n - x) * 2이므로 dp[n - x] * 2
  for (let i = 4; i <= n; i += 2) {
    dp[i] = (dp[i - 2] * 3) % MOD;

    for (let j = 4; j <= i; j += 2) {
      dp[i] = (dp[i] + dp[i - j] * 2) % MOD;
    }
  }

  return dp[n];
}