백준 9009번) 피보나치 (JAVA)

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

9009번: 피보나치

 

문제

피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다. 

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

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

 

#알고리즘

수학

그리디  알고리즘

 

#풀이방법

 

말 그대로 그리디적으로 풀었다.

 

주어진 숫자 직전까지 fibo함수를 계속 구해 주어진 숫자를 넘을 경우, 

바로 그 직전값을 넣어 빼준다.

 

처음에는 fibo 함수를 메모이제이션 기법을 쓰지 않고 제출했더니 시간초과가 나서

메모이제이션을 활용하여 fibo 함수를 구할 때  적용하였더니, 바로 문제가 풀렸다.

 

 

int num = sc.nextInt();
            
            ArrayList<Integer> fiboList = new ArrayList<>();
            
            while(num != 0) {
                
                int k = 0;
                
                for(int j=0; fibo(j) <= num; j++) {
                    k = j;
                }//fibo(j)가 num보다 클 경우 바로 직전 값을 추가해준다.
                
                
                fiboList.add(fibo(k));
                num -= fibo(k);
                //추가 후 제거
                
                
                
            }//num이 0이 될 때까지 계속 진행
            
            
            for(int j=fiboList.size()-1; j>-1; j--)
                System.out.print(fiboList.get(j)+" ");
            //큰 값부터 넣었으므로 역순으로 출력

 

이런식으로 num이 0이 될 때까지

계속 num보다 크지 않는 바로 직전 값을 리스트에 넣고 num에서 빼준후

num이 0이 될 때까지 계속 진행해준다.

 

 

#전체 코드

import java.util.*;
//2t
 
public class Main {
    
    static int[] dp = new int[100];
    //메모이제이션을 위하 dp 배열
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
    
        int T = sc.nextInt();//테스트케이스
        
        for(int i=0; i<T; i++) {
            
            int num = sc.nextInt();
            
            ArrayList<Integer> fiboList = new ArrayList<>();
            
            while(num != 0) {
                
                int k = 0;
                
                for(int j=0; fibo(j) <= num; j++) {
                    k = j;
                }//fibo(j)가 num보다 클 경우 바로 직전 값을 추가해준다.
                
                
                fiboList.add(fibo(k));
                num -= fibo(k);
                //추가 후 제거
                
                
                
            }//num이 0이 될 때까지 계속 진행
            
            
            for(int j=fiboList.size()-1; j>-1; j--)
                System.out.print(fiboList.get(j)+" ");
            //큰 값부터 넣었으므로 역순으로 출력
            
            
            System.out.println();
            
        }
        
    }
    
    public static int fibo(int n) {
        
        if (n <= 1)            
            return n;
        else if(dp[n] != 0)
            return dp[n];
        else
            return dp[n] = fibo(n-2) + fibo(n-1);
        
    }//시간초과 방지를 위해 메모이제이션 기법을 활용하여 fibo 값을 구한다.
    
    
 
}