9009

날짜 : 2022. 11. 23

사용 언어 : python

 

문제

 

 

코드

import sys
f = [0] * 100  # 피보나치 수열
f[0] = 0
f[1] = 1
f[2] = 1
for i in range(3, len(f)):
    f[i] = f[i-1] + f[i-2]

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline()) # 정수 입력
    ans = list() # 결과값 리스트
    i = 1
    while n > 0:
        if f[i] > n:  # 처음으로 큰 값 발견
            ans.append(f[i-1])  # 결과 리스트에 추가
            n = n - f[i-1]  # 빼줌
            i = 0
        i += 1
    for i in range(len(ans)-1, -1, -1): print(ans[i], end=" ")
    print()

 

 

풀이

- 먼저 피보나치 수열을 DP로 구현하여 리스트 생성

- 테스트케이스 수 입력 후 n값을 입력

- 입력받은 수보다 작은 피보나치 수열의 수 중 가장 큰 수를 찾은 후 차감하는 것을 반복한다.

- 그리고 그 수를 ans 리스트에 삽입 한 후 while문을 탈출한 이후에 역순으로 출력

 

 

 

알게된 점

-