백준 2193 < 이친수 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

- 음이 아닌 정수 N이 주어진다.

- 이친수의 조건

1. 11이 2번 등장하지 않음

2. 1과 0으로 만 이루어짐

 

- N 자리의 이친수가 몇개 존재하는지 갯수를 출력하라

 

N = 1 일때는

1

 

N = 2 일때는

10

 

N = 3 일때는

100 101

 

이것을 종합해보면, N = i 일 때,

i - 1의 이친수 들에 0과 1을 붙여서 가능한 것이 생성되는 것을 알 수 있다

 

그리고 규칙성을 쉽게 찾을 수 있다

dp(i) = dp(i - 2) + dp(i - 1)

 

이를 바탕으로 배열을 길게 늘이지 않고, 변수를 바꿔나가는 방법으로 최적화해본다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = 0;

rl.on("line", (line) => {
  input = line;
}).on("close", () => {
  const N = +input;
  let prevprev = 1n;
  let prev = 1n;
  let current = 0;
  const dp = (num) => {
    if (num <= 2) return prev;
    for (let i = 3; i <= N; i++) {
      current = BigInt(prev + prevprev);
      prevprev = prev;
      prev = current;
    }
    return current;
  };
  console.log(dp(N).toString());
});