[실버] 2×n 타일링 2 (11727번)_JS

문제

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

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

 

입력

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

 

출력

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

 

---

1. 기준이 되는 arr를 만든다. (여기서 [0], [1]는 미리 적어줘야 함)

2. 공식대로 input까지 arr를 채운다.

3. 출력한다.

 

여기서 2. 의 공식이란 아래와 같다.

예로, 3을 만드는 경우의 수 = ( 1 [1를 만드는 경우의 수] * 2 ) + 3 [2를 만드는 경우의 수] = 5

 

코드는 아래와 같다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = +input;

const standard = [1, 3, 5]

for (let i = 3; i < input; i++) {
    standard[i] = (standard[i - 2] * 2 + standard[i - 1]) % 10007;
}

console.log(standard[input - 1])