[백준] 11727 2×n 타일링 2 Node.js

문제

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

---

문제풀이

• 피보나치 수열과 같이 문제에서 주어진 조건에도 패턴이 있어, 점화식을 이용한다.
• 2 x 1 타일을 2개 합치면 2 x 2가 된다.
• 1 x 2 타일을 2개 합쳐도 2 x 2가 된다.

n(1) ⇒ 1가지

• (2 x 1) x 1

n(2) ⇒ 3가지

• (2 x 1) x 2
• (2 x 2) x 1
• (1 x 2) x 2

n(3) ⇒ n(2) + (2 x n(1))) = 3가지 + 2 x 1가지 = 5가지

• (2 x 1) x 2 + (1 x 2) x 1
• (2 x 2) x 1 + (1 x 2) x 1
• (1 x 2) x 2 + (1 x 2) x 1
• (1 x 2) x 1 + (2 x 1) x 2
• (1 x 2) x 1 + (2 x 2) x 1

n(4) ⇒ n(3) + (2 x n(2))) = 5가지 + 2 x 3가지 = 11가지

👉🏻 n(x) = n(x - 1) + (2 * n(x - 2))

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const n = +require('fs').readFileSync(filePath).toString().trim();
const dp = [0, 1, 3];

for (let i = 3; i <= n; i++) {
  dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
}
console.log(dp[n]);