문제 정의

• 2n 크기의 직사각형을 1x2와 2x1타일로 채우는 방법의 수를 dp[n] 이라고 정의

Base Cases

• dp[0]: 2x0 크기의 직사각형을 채우는 방법은 1개 (아무것도 채우지 않는 경우)
• dp[1]: 2x1 크기의 직사각형을 채우는 방법은 1개 (2x1 타일 하나로 채우는 경우)

점화식

• 2xn 직사각형을 채우는 방법을 두 가지로 나눌 수 있다.

  1. 마지막 열을 세로로 1x2 타일 하나로 채운 경우: 남은 타일링 문제는 2x(n-1)크기의 직사각형을 채우는 방법으로 바뀜
  2. 마지막 두 열을 가로로 2x1 타일 두 개로 채운 경우: 남은 타일링 문제는 2x(n-2)크기의 직사각형을 채우는 방법으로 바뀜

  이 두가지로 다음과 같은 점화식을 만들 수 있다.

  dp[n] = dp[n−1] + dp[n−2]

구현

const run = (numbers: number[]) => {
  const result = [];
  const maxNumber = Math.max(...numbers);
  const dp = new Array(maxNumber + 1).fill(0);

  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= maxNumber; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
  }

  for (const number of numbers) {
    result.push(dp[number]);
  }

  return result.join('\\n');
};

console.log(run(input));

• base case와 점화식을 세우는 것이 dp 문제 풀이의 핵심이다.