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

문제

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

---

문제풀이

• 2×1 크기의 직사각형을 채우는 방법은 1가지
• 2×2 크기의 직사각형을 채우는 방법은 2가지 (가로로 2개의 타일 또는 세로로 2개의 타일)이다.
• 그리고 그 다음 크기의 직사각형을 채우는 방법은 이전 크기의 직사각형을 채우는 방법의 수에 의존하게 된다.
• 즉, n = 1인 경우부터 그림을 그려보면 dp[n]의 경우의 수는 dp[n-1] + dp[n-2]이 된다는 패턴을 파악할 수 있다. 이러한 점에서 아래의 피보나치 수열과 유사한 패턴을 가진다. F(n) = F(n-1) + F(n-2)
  • F(1) = 1
  • F(2) = 2
  • F(3) = F(1) + F(2) = 3
  • F(4) = F(2) + F(3) = 5
  • F(5) = F(3) + F(4) = 8
• 따라서 ‘2×n 타일링’ 문제는 동적 계획법을 사용하여 피보나치 수열의 값을 찾는 것과 유사한 방식으로 해결할 수 있다.

✅ 답안

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

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