[Java] 백준 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 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

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

입력

입력 데이터는 표준입력을 사용한다. 입력은 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

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	
	private static int T, N;
	private static int []dp;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		T=Integer.parseInt(br.readLine());
		dp=new int[47];	// N의 범위는 1,000,000,000이고, dp[46]=1,836,311,903이므로, dp는 최대 46까지만 저장하면 됨
		dp[0]=0;
		dp[1]=1;
		for(int t=1;t<=T;t++) {
			N=Integer.parseInt(br.readLine());
			int idx=1;
			for(int i=2;i<=46;i++) {	// N의 범위까지 피보나치 값 저장
				if(dp[i-1]>=N) break;
				dp[i]=dp[i-1]+dp[i-2];
				if(dp[i]<=N) idx=i;
			}
			int num=N;
			Stack<Integer> stack=new Stack<>();
			while(num>0 && idx>0) {	// N 이하의 값들 중 가장 큰 것부터 피보나치 값을 N에서 빼면서 0이 되는 조합을 찾아줌
				if(num-dp[idx]>=0) {
					stack.add(dp[idx]);	// 가능한 값들을 큰 것부터 스택에 넣음
					num-=dp[idx];
				}
				idx--;
			}
			while(!stack.isEmpty()) {	// 스택의 값들을 하나씩 꺼내서 출력함
				System.out.print(stack.pop()+" ");
			}
			System.out.println();
		}
	}

}

1. 피보나치 값들 중 1,000,000,000이하인 최대 값을 찾아줍니다 -> fibo(45). 따라서 피보나치 값을 저장할 dp 배열의 범위를 약간 넉넉하게 47로 설정합니다

2. dp에 N보다 작은 피보나치 값들을 전부 저장합니다

3. 저장된 피보나치 값들 중 큰 것부터 차례로 N에서 빼주며 0이 될때까지 반복합니다.

4. 3의 과정에서 선택된 값들을 스택에 저장합니다.

5. 스택에 저장된 값들을 하나씩 꺼내어 출력합니다. 스택에 저장할 때 큰 값부터 넣어줬으므로 이때 나오는 값들은 오름차순으로 출력됩니다.