[ACM-ICPC][BOJ] 9009 - Fibonacci Numbers

안녕하세요.

여행벌입니다.

이번 포스팅에서는 ACM-ICPC 2012 예선전 D번 문제를 다뤄보겠습니다.

---

[문제해석]

어떤 숫자가 주어졌을 때, 그 수를 피보나치 수들의 합으로 표현해라. 이때, 가장 적은 개수의 합으로 표현해라.

 

[알고리즘설계]

1. 피보나치의 재귀식을 이용해 피보나치 수들을 먼저 배열에 구한다.

2. 피보나치 배열을 순회하며 주어진 숫자보다 작지만 가장 근접한 피보나치 수를 찾고, '주어진숫자 - 피보나치수'를 반복해주며, 이 수들을 저장한다.

3. 저장된 수들을 출력한다.

#include<cstdio>

int fibonachi_list[47] = { 0,1 };

int main(void) {
	for (int i = 2; i < 47; i++)
		fibonachi_list[i] = fibonachi_list[i - 1] + fibonachi_list[i - 2];
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int ninput;
		scanf("%d", &ninput);
		int count = 0, temp[100] = {};
		while (ninput) {
			for (int j = 0; j < 47; j++) {
				if (fibonachi_list[j] <= ninput && ninput < fibonachi_list[j + 1]) {
					temp[count] = fibonachi_list[j];
					count++;
					ninput -= fibonachi_list[j];
					break;
				}
			}
		}

		for (int j = 0; j < count; j++)
			printf("%d ", temp[count - 1 - j]);
		printf("\n");
	}
}

피보나치 수는 기존의 수들의 합으로 이루어졌기 때문에, 최소한의 개수를 이용하려면 단순히 큰 수부터 빼주면 된다.

피보나치 수가 아닌 어떤 임의의 수열이었으면, 문제가 어려웠을 것 같다.

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실분은 댓글로 자유롭게 남겨주셔도 좋을것 같습니다! 
감사합니다.