2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
2
3
8
171
12
2731
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]);