백준 1904 JS 풀이

구하는 값

00, 1 을 이용해서 표현할 수 있는 n자릿수의 2진수 개수

핵심 아이디어

n에 1,2,3,4,5, … 넣다보면 규칙이보임 이거 피보나치다..!

그 뒤는 스무스하게 피보나치 구현

코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split("\n")

const n = input[0] * 1;

// 점화식이 피보나치랑 동일

const d = new Array(n + 1).fill(0);
d[1] = 1;
d[2] = 2;

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