DP - 2*N 타일링

문제 (백준 11726)

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

---

🚀문제 접근

n이 4일때까지만 직접 그려보면 피보나치 수열임을 알 수 있고 이를 기반으로 점화식을 세울 수 있다.

하지만 다른 원리로 점화식까지 도출하는 과정이 있기에 정리하고자 한다.

 

 

2*N의 직사각형을 채우는 방법은 2*N-1 까지 직사각형을 채우고 옆에 사각형을 붙이는 방법 하나와 2*N-2 까지 직사각형을 채우고 그림과 같이 사각형을 배치하는 방법이 있다. 그런데 2번째 배치는 이미 2*N-1에서 구한 값이기 때문에 생략한다. 따라서 2*N 직사각형을 채우는 방법은 2*N-1 직사각형을 채우는 방법 + 2*N-2 직사각형을 채우는 방법이 된다.

따라서 다음과 같이 점화식을 도출할 수 있다.

F(N) = F(N-1) + F(N-2) 

 

🛠코드

let n = Number(require('fs').readFileSync(0).toString().trim());

function solution() {
  const dy = [];
  dy[0] = 0;
  dy[1] = 1;
  dy[2] = 2;

  for (let i = 3; i <= n; i++) {
    dy[i] = (dy[i - 1] % 10_007) + (dy[i - 2] % 10_007);
  }

  return dy[n] % 10_007;
}

console.log(solution());