[백준 - C#] 9009번 피보나치

문제링크

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

9009번: 피보나치

 

문제

피보나치 수 ƒ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 등으로 나타낼 수 있다.
이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 
하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

입력 데이터는 표준입력을 사용한다.
입력은 T 개의 테스트 데이터로 구성된다.
입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다.
각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000. 

출력

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

 

문제정리

1. 피보나치수는 ƒK = ƒK-1 + ƒK-2로 정의
2. 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수

이번 문제의 경우 피보나치 수들의 합이 주어진 정수와 같은 최소 개수를 구하는 문제입니다.

일단 데이터에 사용하는 하나의 정수 n의 크기가 그렇게 크지 않기 때문에 피보나치의 값을 미리 계산하였습니다.

계산한 값을 가지고 제일 큰 수부터 값을 찾아 내어야 최소개수를 적게 할 수 있는데

예를들어, 100의 경우 89, 8, 3 대신 55, 34, 8, 3 을 쓰게되면 최소 개수의 차이가 나기 때문입니다. 

 

이번 문제는 그리디 알고리즘으로 풀이를 하였습니다. 더 자세한 내용은 아래 C# 코드에서 확인 해보실 수 있습니다.

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int T = int.Parse(reader.ReadLine());
    List<int> f = new List<int>();
    // 피보나치 정의를 사용하기 위해 0과 1은 미리 입력
    f.Add(0);
    f.Add(1);
 
    int index = 2;
    while (true)
    {
        int value = f[index - 1] + f[index - 2]; // 피보나치 계산
        if (value > 1000000000) // 조건에 따라 해당 하는 값보다 크다면 무의미
            break;
 
        f.Add(f[index - 1] + f[index - 2]); // 계산한 값을 f리스트에 저장
        index++;
    }
 
    List<int> result = new List<int>();
    int count = f.Count;
    for (int i = 0; i < T; i++)
    {
        int input = int.Parse(reader.ReadLine());
        int listIndex = count - 1; // 피보나치 제일 큰 수부터 index 설정
 
        while (input > 0) // 입력 받은 값보다 작아지면 반복문 탈출
        {
            for (int j = listIndex; j > -1; j--) // 피보나치의 제일 큰 수부터 시작
            {
                // 입력 받은 값에 피보나치 값을 빼서 나온 값이 0보다 크다면 더할 수 있다.
                // 0보다 작다면 더할 수 없는 값
                if (input - f[j] >= 0)
                {
                    result.Add(f[j]);
                    input -= f[j];
                }
            }
        }
 
        int last = result.Count - 1;
 
        // 제일 작은 수부터 출력
        for (int j = last - 1; j >= 0; j--)
            writer.Write(result[j] + " ");
 
        writer.WriteLine();
        result.Clear();
    }
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.