[백준/Python] (S1) 피보나치 - 9009

Baekjoon Online Judge의 9009번 피보나치 문제의 Python 풀이입니다.

9009번: 피보나치

💻코드

# 미리 계산된 피보나치 수열의 리스트
fibonacci = [701408733, 433494437, 267914296, 165580141, 102334155, 63245986, 39088169, 24157817, 14930352, 9227465,
             5702887, 3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711,
             10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1]

test_cases = int(input())
for _ in range(test_cases):
    n = int(input())

    # 주어진 정수를 표현하는 데 사용된 피보나치 수들을 저장할 리스트
    result = []
    for fibonacci_number in fibonacci:
        # 현재 피보나치 수가 목표 정수 이하일 경우, 목표 정수에서 해당 피보나치 수를 뺀다
        if fibonacci_number <= n:
            n -= fibonacci_number
            # 사용된 피보나치 수를 리스트에 추가
            result.append(fibonacci_number)
    # 결과 출력. 역순으로 출력하여 증가하는 순서로 표시
    print(*result[::-1])

🧠풀이

이 문제는 주어진 정수를 최소 개수의 피보나치 수들의 합으로 나타내는 방법을 찾는 것이다. 이를 해결하기 위해, 큰 피보나치 수부터 시작하여 주어진 수보다 작거나 같은 가장 큰 피보나치 수를 찾고, 이를 주어진 수에서 빼준다. 이 과정을 반복하여, 최종적으로 0이 될 때까지 사용된 피보나치 수들을 기록한다.

그리디 알고리즘은 매 순간 최적의 선택을 함으로써 전체에서도 최적의 결과를 도출하려는 전략이다. 본 문제에서는 각 단계에서 주어진 수보다 작거나 같은 가장 큰 피보나치 수를 선택하는 것이 그리디한 선택이다.

🤔느낀 점

이 문제를 통해 피보나치 수열의 성질과 그리디 알고리즘의 개념에 대해 더 깊이 이해할 수 있었다.