백준 9009: 피보나치

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

9009번: 피보나치

13조 (수도권)

9009_피보나치

문제 설명

입력된 T개의 양의 정수 n 를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타낸다.

=> 입력: T, n 차례로 입력

=> 출력: n의 최소 개수의 피보나치 수의 합을 차례로 출력

풀이 방법

n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고 그 수를 n에서 뺀 나머지에 대해 또 이 시행을 반복.

 

l = [1,2]//피보나치 수열은 첫번째 항이 1, 두번째 항이 2 이므로 그 배열을 저장해 둔다.
for i in range(2, 46): //n의 최대 수보다 작은 마지막 항인 46번째 항까지 더한다.
    l.append(l[i-2]+l[i-1]) // 피보나치 수를 배열 l에 덧붙인다.
T = int(input()) //T 입력 받기

for j in range(T):
    n = int(input())
    result=[]// result를 저장할 배열을 만든다.
    while(n): // n이 1-1 = 0이 되는 순간 while 문 break 
        for k in range(46):
            if(p[k]<=n)://n보다 작거나 같은 수중 가장 큰 수를 찾는 코드
                t = p[k]
        n -= t // 그 수를 n에서 뺀 나머지를 n에 다시 저장
        result.append(t)
        result.sort()
    for b in range(len(result)): // 출력 
        print(result[b], end=' ')