[BOJ/백준 9009][C++] 피보나치

문제

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

 

문제 내용

하나의 양의 정수를 최소한의 피보나치 수들의 합으로 나타내면 된다.

 

문제 풀이

일단 먼저 피보나치 배열을 만들어두었다.
입력이 1,000,000,000 이하의 수로 들어오기 때문에, 피보나치 수를 45 정도까지 구해두면 문제를 푸는데 문제가 없었다.

숫자를 입력받고 나서는, 반복문을 통해 문제를 해결해 나갔다.
하나의 테스트 데이터에 대해, 역순으로 피보나치 수와 비교하며 진행했다. (코드를 보면 이해가 갈 것이다.)

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//피보나치 배열 만들어두기 - 대충 한 45정도면 해결된다고 한다.
	int fib[46] = { 0, 1 };
	for (int i = 2; i < 46; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}

	//입력
	int n,tmp;
	cin >> n;
	vector<int>v;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	//문제 해결
	
	for (int i = 0; i < v.size(); i++) { //테스트 데이터 별로 계산
		vector<int>result;

		while (v[i]) {
			for (int j = sizeof(fib)/sizeof(*fib)-1; j >= 0; j--) { //역순으로 비교
				if (fib[j] > v[i]) continue; //피보나치 수와 비교
				result.push_back(fib[j]);
				v[i] -= fib[j];
				if (v[i] <= 0) break;
			}
		}
		sort(result.begin(), result.end()); //작은 수부터 출력하기 위해 정렬
		
        //결과 출력
		for (int k = 0; k < result.size(); k++) {
			cout << result[k] << ' ';
		}
		cout << '\n';
	}

}

 

문제 코드 설명

1) 입력

데이터 개수 n을 입력받고, vector에 n개의 테스트 데이터를 입력받는다.

 

2) 문제 해결

각각의 테스트 케이스에 대해 풀이를 진행하고 결과를 출력한다.

테스트 케이스 v[i]를 피보나치 수와 비교하며, v[i]가 피보나치 수보다 작을 때 result 배열에 저장하고 v[i]를 감소시킨다.
v[i]가 0이 되면 반복문을 탈출하여, 결과를 출력하면 된다. (이때 오름차순으로 출력하기 위해 sort함수를 사용한다.)