[백준][자바스크립트] 9009번_피보나치

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

문제

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000. 

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다. 

예제 입력 1

4
100
200
12345
1003

예제 출력 1

3 8 89
1 55 144
1 34 377 987 10946
3 13 987

 

---

문제 풀이

서로 다른 피보나치 수의 합으로 표현할 때, 최소 개수의 피보나치 수를 찾는 문제로, 그리디 알고리즘을 사용한다.
모든 양의 정수는 서로 다른 피보나치 수의 합으로 유일하게 표현 된다.
가장 큰 피보나치 수부터 차례로 선택하여 합을 구성하면 최소 개수를 보장한다.

• 10억(1e9) 이하의 모든 피보나치 수를 미리 계산
• 주어진 수 n에서 가장 큰 피보나치 수 빼기
• 큰 수부터 선택했으므로, 결과를 오름차순으로 정렬해 출력하기

소스코드

[수도 코드]

입력:
  T (테스트 케이스 수)
  data = [각 테스트 케이스 값]

초기화:
  fibo = [0, 1]  # 피보나치 수열 초기값
  while fibo의 마지막 값 ≤ 1e9:
    fibo에 다음 피보나치 수 추가 (fibo[-1] + fibo[-2])

각 테스트 케이스 처리:
  for 각 테스트 값 n in data:
    result = []  # 사용된 피보나치 수 저장
    j = fibo의 마지막 인덱스  # 가장 큰 수부터 검사

    while n > 0:
      if fibo[j] ≤ n:
        n -= fibo[j]
        result에 fibo[j] 추가
      j -= 1  # 다음으로 작은 피보나치 수 검사

    출력:
      결과를 오름차순으로 정렬 후 출력

 

[코드 구현]

const fs = require('fs');
const [T, ...data] = fs.readFileSync('input.txt').toString().split('\n').map(Number);

const fibo = [0, 1];
while (fibo[fibo.length - 1] <= 1e9) {
  fibo.push(fibo[fibo.length - 1] + fibo[fibo.length - 2]);
}

for (let i = 0; i < T; i++) {
  let n = data[i];
  const result = [];
  let j = fibo.length - 1;

  while (n > 0) {
    if (n >= fibo[j]) {
      n -= fibo[j];
      result.push(fibo[j]);
    }
    j--;
  }

  console.log(result.reverse().join(' '));
}

• reverse() 메서드는 배열을 뒤집는다.