[백준2193_자바스크립트(javascript)] - 이친수

🔴 문제

이친수

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));
const db = new Array(n).fill(0);
// 0 개수 , 1 개수
db[1] = [0n, 1n];

for (let i = 2; i <= n; i++) {
  const [cnt0, cnt1] = db[i - 1];
  db[i] = [cnt0 + cnt1, cnt0];
}

console.log((db[n][0] + db[n][1]).toString());

🟢 풀이

⏰ 소요한 시간 : 35분

그림으로 1자리 수부터 5자리 수까지 규칙을 찾아보니 0으로 끝나는 수는 끝에 1과 0을 붙여 2가지 수를 만들 수 있고 1로 끝나는 수는 1을 못붙여 0만 붙여주면 된다.
그래서 db에 0의 개수와 1의 개수를 저장시켜 준다.
1자리 수 일때 이친수는 db[1] = [0, 1] 이고 이로 점화식을 세워주면 db[i] = [db[i - 1][0] + db[i - 1][1], db[i - 1][0]]이 된다.
처음에 틀렸습니다가 나왔는데 n의 최대값 90을 찍어보니 숫자가 너무 큰 값이라 올바르게 계산되지 않는 듯 했다. 그래서 값을 BigInt 형태로 변경 해주니까 정답!

🔵 Ref