백준 9009번 C언어 풀이

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

9009번: 피보나치

입력받은 자연수를 서로 다른 피보나치 수의 합으로 분해하는 문제.

 

재귀함수로 풀이했다.

 

역시 재귀함수는 중간에 잘못 꼬이면 고치기가 힘든 것 같다.

#include <stdio.h>
int find_max_fibo(int n)
{
    int a1 = 0, a2 = 1;
    int fibo = 1;
    while (a1 + a2 <= n) {
        fibo = a1 + a2;
        a1 = a2;
        a2 = fibo;
    }
    return fibo;
}

void find_fibos(int n)
{
    if (n == 1) { 
        printf("1 ");
        return; 
    }
    else {
        int f = find_max_fibo(n);
        if (f == n) {
            printf("%d ", f);
            return;
        }
        else if (n - f > 0) {
            find_fibos(n - f);
        }
        printf("%d ", f);
    }
}

void main()
{
    int n_tests;
    int n, max_fibo;
    scanf("%d", &n_tests);
    while (n_tests--) {
        scanf("%d", &n);
        find_fibos(n);
        printf("\n");
    }
}