BOJ/백준-9009-python

문제📖

풀이🙏

• 입력 데이터는 표준입력을 사용한다.
• 입력은 T개의 테스트 데이터로 구성된다.
• 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다.
• 각 테스트 데이터에는 하나의 정수 n이 주어진다.
• 출력은 표준출력을 사용한다.
• 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다.
• 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치수들을 증가하는 순서로 출력하라.

코드💻

# boj, 9009 : 피보나치, python3
# 그리디 알고리즘 
import sys
    
def solution(n):
    fibonacci = [0, 1]
    result = []
    
    for i in range(2, 45):
        fibonacci.append(fibonacci[i-2] + fibonacci[i-1])
    
    for i in range(len(fibonacci)-1,0,-1):
        if fibonacci[i] <= n:
            n -= fibonacci[i]
            result.append(fibonacci[i])
            
    result.sort()
        
    return ' '.join(map(str, result))


T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    print(solution(n))

결과😎

출처 && 깃허브📝

boj
github