[baekjoon] 백준 9009번(파이썬): 피보나치

문제

9009번: 피보나치

- 피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다.

- 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다.

- 하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다.

- 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다.

- 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

- 하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

- 테스트 데이터의 수를 나타내는 정수 T 가 주어진다.

- 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000

- 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다

알고리즘

- 테스트를 입력받는다.

- 피보나치 초기값 0 과 1을 설정한다.

- 피보나치 번호, 45가 10억을 넘기 때문에 2부터 46까지 반복하여 피보나치 수를 리스트에 추가한다.

- 각 테스트별로 피보나치 수를 출력한다.

- 제일 큰 피보나치 수부터 반복하여 n보다 작을 경우 res 리스트에 피보나치 수를 추가한다.

- 정수를 피보나치 수만큼 빼주어 다시 반복한다.

- 이때 n이 0이면 res 리스트를 오름차순으로 정렬하여 순서대로 출력한다. 

코드

import sys

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

# 피보나치 초기 값
fibonacci = [0, 1]

# n = 45, 피보나치 = 1134903170
for x in range(2, 46):
    fibonacci.append(fibonacci[x-2] + fibonacci[x-1])

# 각 테스트 별로 피보나치 수 출력
for _ in range(t):
    n = int(sys.stdin.readline())
    res = []

    # 제일 큰 수에 피보나치 수부터 반복하여 비교한다.
    for i in range(45, 0, -1):

        # 피보나치 수가 정수보다 작은 경우 res 리스트에 피보나치 수를 추가하고
        # 정수를 피보나치 수만큼 빼준다.
        if fibonacci[i] <= n:
            res.append(fibonacci[i])
            n -= fibonacci[i]

            # 더이상 빼줄 정수가 없는 경우
            if n == 0:
                # res 리스트를 오름차순으로 정렬하여 순서대로 출력한다.
                res.sort()
                for result in res:
                    print(result, end=" ")

                break

github

junjange/CodingTest