백준 11727번 2xn 타일링2

내가 푼 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

let n = Number(input[0]);
let arr = new Array(n+1).fill(0);
arr[1] = 1;
arr[2] = 3;

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

console.log(arr[n]);

규칙찾느라 40분걸림.

1: 1개
2: 3개
3: 5개 = (3+1+1)
4: 11개 = (5+3+3)
5: 21개 = (11+5+5)
6: 43개 = (21+11+11)

규칙은 F(n) = F(n-1) + F(n-2) + F(n-2) 이다.
피보나치 수열구하듯이 풀면된다.