BOJ - 9009 피보나치

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

티어 : 실버 1 

문제 유형 : 그리디 알고리즘 (탐욕법)

문제 풀이 

피보나치 수열이란? 
f(k) = f(k-1) + f(k-2)로 정의 될 수 있는 수열을 일컫는다. 즉, 예를 들어 정수 100을 생각해보면 여러 경우가 있을텐데 예시를 들면 아래와 같다
1. f(4) + f(6) + f(11) = 3 + 8 + 89 = 100

2. f(1) + f(3) + f(6) + f(11) = 1 + 2 + 8 + 89 = 100

이 문제는 위와 같은 서로 다른 피보나치의 갯수를 구하는 것이다.

 

문제 접근 방법 

= 문제 유형처럼 그리디 알고리즘 , 즉 탐욕법을 사용해서 앞에서 부터 가장 최선의 선택으로 채워 나가는 방식을 선택한다.

1. 피보나치 수 구하기 : 먼저 주어진 수보다 작은 피보나치 수들을 모두 구한다.

2. 가장 큰 피보나치 수 선택 : 피보나치 수들의 리스트를 거꾸로 탐색하면서, 현재 수에서 가장 큰 피보나치 수를 선택하여 빼준다.

3. 남은 수 처리 : 남은 수에 대해서도 같은 과정을 반복함

4. 결과 출력 : 오름차순으로 출력해야 하기 때문에 마지막에 선택한 피보나치 수들의 리스트를 정렬하여 출력 해준다.

 

왜 큰 수에서 빼는가? 

= 그리디 알고리즘의 핵심이다 당장 매 순간 가장 좋은 선택을 하여 최종 해결책을 얻는 방법인데 , 이 문제를 예시로 들어보자 예를 들어 100이라는 숫자가 있다고 하자. 이 숫자를 피보나치 수들의 합으로 표현한다고 가정해보자

피보나치 수 = 1,1,2,3,5,8,13,21,34,55,89,144... 등 정해진 규칙이 있는 정해진 숫자들이다.

100보다 작거나 같은 가장 큰 수는 89이다. 만약 여기서 89를 빼면 

100 - 89 = 11 

같은 과정을 반복하자. 11 다음 가장 큰 수는 8이다 

11 - 8 = 3

0이 될 때 까지 계속 반복한다

3 - 3 = 0

 

이렇게 나타내면 89 , 8 , 3 이 남는다. 즉, 100 = 89 + 8 + 3이 된다. 작은 수부터 생각해보면 중복된 피보나치 수 (1,1,2,3 .. )등을 선택해야 하기 때문에 생각할 게 많아진다. 

ex)  100 - 1 = 99 , 99 -1 = 98 , 98 - 1 = 97 ,,,,,

 

따라서 코드로 살펴보자

const fs = require("fs");
let input = fs.readFileSyne("/dev/stdin").toString().split("\n");
// 10억 이하의 피보나치 수열 미리 생성 
let pibo = [];
pibo.push(1); // 첫 번째
pibo.push(1); // 두 번째

// 10억 이하까지 계속 반복
while(pibo[pibo.length -1] <= 1e9) {
    pibo.push(pibo[pibo.length - 2] + pibo[pibo.length - 1]);
 }
 // 테스트 케이스 수
 let n = Number(input[0]);
 
 for(let i=1;i<=n;i++){
    let num = Number(input[i]);
    let result = [];
    let maxIndex = pibo.length -1; // 가장 큰 피보나치 수의 인덱스
    
    // 그리디 알고리즘으로 가장 큰 피보나치 수부터 빼기
    while(num>0){
        if(num >= pibo[maxIndex]){
            num -= pibo[maxIndex];
            result.push(pibo[maxIndex]);
        }
        maxIndex--;
     }
     
     // 결과를 오름차순으로 정렬하고 출력
     console.log(result.reverse().join(" "));
   }

 

 

핵심 알고리즘 예시

// 그리디 알고리즘으로 가장 큰 피보나치 수부터 빼기
while (num > 0) {
    if (num >= pibo[maxIndex]) {
        num -= pibo[maxIndex];  // 피보나치 수를 num에서 빼기
        result.push(pibo[maxIndex]);  // 그 피보나치 수를 결과에 추가
    }
    maxIndex--;  // 그 다음으로 작은 피보나치 수를 확인
}



/*
if (100 >= 89) {
    num -= 89;  // 100 - 89 = 11
    result.push(89);  // 89를 결과에 추가
}
maxIndex--;  // 그 다음 작은 피보나치 수로 이동
*/

/* 
if (11 >= 8) {
    num -= 8;  // 11 - 8 = 3
    result.push(8);  // 8을 결과에 추가
}
maxIndex--;  // 다음 작은 피보나치 수로 이동
*/

/*
if (3 >= 3) {
    num -= 3;  // 3 - 3 = 0
    result.push(3);  // 3을 결과에 추가
}
*/

 

시간복잡도 : O(Tlog n) T : 테스트 케이스 수 , n : 주어진 숫자 크기 

공간복잡도 : O(1)