[백준] 11727

2 * n 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

const square = () => {
  let n = parseInt(require("fs").readFileSync("/dev/stdin").toString().trim());
  let dp = Array.from({ length: n }, (v) => 0);
  dp[0] = 1;
  if (n > 0) dp[1] = 3;
  for (let i = 2; i < n; i++) {
    dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;
  }
  console.log(dp[n - 1]);
};

square();

반성회

1. 길이 n의 dp 배열 생성
2. dp[i] 는 2 * i 크기의 직사각형을 채우는 방법의 수를 의미한다
   • 2 * 1 타일을 가로로 2개 배치하거나, 2 * 2 타일을 배치하게 되면 2 * (i - 2) 크기의 직사각형에 배치해야 하므로 2 * (i - 2) 크기 직사각형을 채우는 경우의 수가 필요 ⇒ dp[i - 2] 의 값이 필요하다
   • 2 * 1 타일을 세로로 1개 배치하면 2 * (i - 1) 크기의 직사각형에 배치해야 하므로 dp[i - 1]의 값이 필요하다
   • 따라서 dp[0], dp[1] 을 직접 초기화해야 함
3. 2 * i 크기의 직사각형을 채우는 경우는
   • 2 * (i - 2) 크기의 직사각형에 2 * 1 크기 타일을 가로로 2개 배치하기
   • 2 * (i - 2) 크기의 직사각형에 2 * 2 크기 타일을 배치하기
   • 2 * (i - 1) 크기의 직사각형에 2 * 1 크기 타일을 세로로 1개 배치하기
4. 따라서 2 * i 크기의 직사각형을 채우는 경우의 수는
   • 2 * (i - 2) 크기의 직사각형을 채우는 경우의 수 * 2와
   • 2 * (i - 1) 크기의 직사각형을 채우는 경우의 수의 합
5. 따라서 dp[i] 는 dp[i - 2] * 2 + dp[i - 1]
6. 최종적으로 2 * n 크기의 직사각형을 채워야 하므로 dp 배열의 마지막 원소 출력