[9009] 피보나치

피보나치 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1110	603	484	52.666%

문제

피보나치 수 ƒ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. 

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다. 

예제 입력 

4
100
200
12345
1003

예제 출력 

3 8 89
1 55 144
1 34 377 987 10946
3 13 987

힌트

N의 크기가 최대 1,000,000,000이기 때문에 피보나치 값이 저 수를 넘기위해서는 대략 40 몇이라는 것을 알 수 있었습니다.

완전탐색으로 한다면 40^2의 시간이 걸리기 때문에 제한 시간 1초에는 충분했습니다.

입력받은 N과 가장 근접한 작은 수를 찾아서 거기서 부터 값을 더해나갑니다.

만약 더할 때 N보다 커진다면 그 수를 빼고 그 다음으로 넘어갑니다.

그리고 더한 수를 순서대로 출력해야 하고 큰 수 부터 더했으므로 스택에 저장했습니다.

0까지 갔는데도 n을 못만들었다면 근접한 작은 수에서 1을 빼고 다시 탐색합니다.!

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
ll fi[MAX_SIZE];
 
int main()
{
    //피보나치 값 미리 구하기
    fi[0] = 1;
    fi[1] = 1;
    for(int i = 2;; i++)
    {
        fi[i] = fi[i - 1] + fi[i - 2];
        if(fi[i] >= 1000000000) break;
    }
 
    int n, t;
    scanf("%d", &t);
 
    while(t--)
    {
        scanf("%d", &n);
 
        int start;
        stack<ll> s; // 출력할 때 쓸 스택
 
        for(start = 0; fi[start] <= n; start++); // n과 가장 근접한 수 찾기
        start--; //fi[start]값이 n을 넘었다면 그 전 값이 가장 근접한 작은 수이기 때문에 1 빼기.
 
        ll sum = 0;
        bool flag = 0;
 
        //탐색하기
        for(int i = start; i >= 0; i--)
        {
            for(int j = i; j >= 0; j--)
            {
 
                sum += fi[j];
                s.push(fi[j]);
 
                if(sum == n)
                {
                    flag = 1;
                    break;
                }
                else if(sum > n)
                {
                    sum -= fi[j];
                    s.pop();
                }
 
            }
 
            if(flag) break;
            else
            {
                sum = 0;
                while(!s.empty()) s.pop();
            }
        }
 
        while(!s.empty())
        {
            printf("%lld ", s.top());
            s.pop();
        }
        puts("");
 
    }
 
    return 0;
 
}
 

나중에 읽었더니.. 제가 한 풀이는 완전 탐색이 아니고 그리디를 이용한 방법이네요...

그래서 완전 탐색으로 다시 한번 풀었습니다.

아래의 코드입니다.

dfs를 이용해서 완전탐색을 해보았습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
int fi[MAX_SIZE];
int n, t;
stack<int> s;
bool flag;
 
void dfs(int idx, int sum)
{
    if(sum > n) return;
    else if(sum == n)
    {
        s.push(fi[idx]);
        while(!s.empty())
        {
            printf("%d ", s.top());
            s.pop();
        }
        puts("");
        flag = 1;
        return;
    }
 
    s.push(fi[idx]);
 
    for(int i = idx - 1; i >= 0; i--)
    {
        dfs(i, sum + fi[i]);
        if(flag) return;
    }
}
 
 
int main()
{
    fi[0] = 1;
    fi[1] = 1;
    for(int i = 2;; i++)
    {
        fi[i] = fi[i - 1] + fi[i - 2];
        if(fi[i] >= 1000000000) break;
    }
 
 
    scanf("%d", &t);
 
    while(t--)
    {
        flag = 0;
        scanf("%d", &n);
 
        int start;
 
        for(start = 0; fi[start] <= n; start++);
        start--;
 
        for(int i = start; i >= 0; i--)
        {
            dfs(i, fi[i]);
            while(!s.empty()) s.pop();
            if(flag) break;
        }
 
    }
 
    return 0;
}