백준 9009 문제
백준 9009 풀이
머리 아파 죽는 줄 알았다. 피보나치 수열을 어떻게 구현할지 몰라서 머리 아파 하던 중에 f(0)이 0이고, f(1)이 1이란 점에서 좀 해답을 찾은 것 같다.
어차피 모든 수는 1을 다 더하면 표현할 수 있기 때문에, 모든 수는 피보나치 수열의 합이다. 그런데, 이걸 가장 적은 피보나치 수열의 합으로 표현하기 위해서는 주어진 수에서 가장 큰 피보나치 수열을 계속 빼 나가면 된다.
아래는 그걸 코드로 구현한 것이다.
# 9009
# 입력 받기
t= int(input())
for _ in range(t):
n = int(input())
# 피보나치 수열 담을 빈 리스트
lst=[]
# 피보나치 수열 처음
b=1 #f(1)
c=0 #f(0)
# 피보나치 수열로 반복 돌리며 최대일 때 빼기
while True:
a= b+c
if n<a:
lst.append(b)
n-=b
if n==0:
break
#피보나치 초기화
b=1
c=0
#피보나치 다음항
else:
c=b
b=a
#역순으로 출력
for i in lst[::-1]:
print(i, end=' ')
print()
No Responses