[BOJ] 9009: 피보나치

BOJ 9009 : 피보나치

9009번: 피보나치

❓문제 설명

---

✨제켄도르프의 정리 (Zeckendorf's Theorem)

모든 양의 정수는 피보나치 수의 유일한 합의 표현으로 나타낼 수 있다.

이때 최소 개수로 나타낼 경우, 피보나치 수는 연속적으로 나타나지 않는다.

---

❗️문제 풀이

이 이론에 착안하여 코드를 작성하였고 아래는 시행착오이다.

import sys
T = int(sys.stdin.readline())
fibo = [0, 1]
answer = [[]for i in range(T)]

for i in range(T):
    N = int(sys.stdin.readline())
    print(N)
    while(N != 0):
        if(N > fibo[-1]):
            fibo.append(fibo[-1] + fibo[-2])
            print(fibo)
        if((N < fibo[-1]) and (N >= fibo[-2])):
            answer[i].append(fibo[-2])
            print(answer)
            N -= fibo[-2]
            print(N)
        continue
    continue

print(answer)

-> ex) 100 -> 89가 걸러지고 11이 걸러지지 않음.

 

# BOJ 9009 피보나치

import sys
T = int(sys.stdin.readline())
fibo = [0, 1]
answer = [[]for i in range(T)]

for i in range(T):
    # print(i)
    N = int(sys.stdin.readline())
    while(N != 0):
        if(N > fibo[-1]):
            fibo.append(fibo[-1] + fibo[-2])
            #print(fibo)
        else:
            for j in range(len(fibo) - 1):
                if N >= fibo[j] and N < fibo[j+1]:
                    answer[i].append(fibo[j])
                    # print(answer)
                    N -= fibo[j]

for i in range(T):
    print(*sorted(answer[i]))

-> 시간초과

# BOJ 9009 피보나치

import sys
T = int(sys.stdin.readline())
fibo = [0, 1]
answer = [[]for i in range(T)]

for i in range(T):
    # print(i)
    N = int(sys.stdin.readline())
    while(N != 0):
        if(N > fibo[-1]):
            fibo.append(fibo[-1] + fibo[-2])
        else:
            for num in reversed(fibo):
                if num <= N:
                    answer[i].append(num)
                    N -= num

for i in range(T):
    print(*sorted(answer[i][:-1]))