#9009 : 피보나치

풀이방법

사용된 것:

정렬

그리디 알고리즘

 

2022.03.05

N의 최댓값까지 커버하려면 $f_{44}$까지만 미리 구해놓으면 된다.

길이가 45인 Long 정수 배열을 선언하고, 이 안에 $f_0$부터 $f_{44}$까지를 미리 다 구해 저장해둔다.

이 피보나치 수 배열을 내림차순으로 정렬한다.

 

입력값으로 수 N이 주어졌다고 하자.

피보나치 수 배열의 앞부터(큰 수부터) 방문하며, N보다 작거나 같은 피보나치 수가 발견되면 즉시 해당 수를 출력할 수 배열에 추가하고, N에서 그 수를 빼준다.

이를 N == 0이 될 때까지 반복한다.

 

이렇게 구해진 수들을 오름차순으로 정렬한 뒤에 출력하면 된다.

 

코드

Java(2022.03.05)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	static int t;	//테스트케이스의 개수
	static int num;	//이번 테스트케이스에 주어진 수
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long[] arr = new long[45];
		arr[0] = 0;
		arr[1] = 1;
		for(int i = 2; i<45; i++) {
			arr[i] = arr[i-2] + arr[i-1];
		}
		
		sb = new StringBuilder();
		t = Integer.parseInt(br.readLine());
		for(int i = 0; i<t; i++) {
			num = Integer.parseInt(br.readLine());
			ArrayList<Long> temp = new ArrayList<>();
			for(int j = 44; j >= 0; j--) {
				if(arr[j]<=num) {
					num -= arr[j];
					temp.add(arr[j]);
					if(num == 0) break;
				}
			}
			Collections.sort(temp);
			for(int j = 0; j<temp.size(); j++) {
				sb.append(temp.get(j) + " ");
			}
			sb.append(System.lineSeparator());
		}
		
		System.out.print(sb);
	}

}