파이썬 그리디 알고리즘 백준 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 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라.

입력

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

출력

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

풀이

하나의 수를 최소의 피보나치 조합 수로 나타내야 한다.

최소한의 조합을 사용하기 위해서는 입력 받은 수보다 작은 피보나치 수 중에 가장 큰 값부터

조합에 더해가면 된다.

따라서 입력값의 범위를 넘지 않는 피보나치 수를 모두 구해 놓는다. pibo

그리고 pibo 리스트를 순회하여 입력값보다 작고 피보나치 수 중에 가장 큰 수를 구하고 ans에 저장한다.

그리고 그 수 만큼 입력값에 빼준다.

이것을 입력값이 0이 될 때 까지 반복해주면 답을 구할 수 있다.

입력값이 0이되고 모든 수를 구하면 수 들을 오름차순으로 출력해야하기 때문에

ans 리스트를 거꾸로 순회하며 출력한다.

 

import sys
t = int(sys.stdin.readline().rstrip("\n"))
pibo=[1,2]
for i in range(2,46):
    pibo.append(pibo[i-1]+pibo[i-2])
for i in range(t):
    n = int(sys.stdin.readline().rstrip("\n"))
    ans = []
    while(n):
        for j in range(46):
            if(pibo[j]<=n):
                temp = pibo[j]
        n-=temp
        ans.append(temp)

    for j in range(len(ans)-1,-1,-1):
        print(ans[j], end=" ")
    print("")