숫자 n이 주어졌을 때, n을 피보나치 수들의 합으로 표현하는 데 필요한 피보나치 수의 최소 개수를 구하는 문제입니다.
예를 들어 입력값이 n = 20이라면 출력은 3이 됩니다. 피보나치 수 [2, 5, 13]을 사용하면 2 + 5 + 13 = 20이 되기 때문입니다.
문제 해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 n 이하에서 가장 큰 피보나치 수를 계속 빼주는 것입니다. 다음 단계를 따릅니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- 피보나치 수열 리스트 fibo를 [1, 1]로 초기화합니다.
- fibo의 마지막 원소가 n 이하일 때까지, 마지막 두 원소의 합을 계속 추가하여 피보나치 수열을 생성합니다.
- n이 0이 아닌 동안 다음을 반복합니다.
- fibo의 마지막 원소가 n보다 크면 리스트에서 제거합니다.
- n에서 fibo의 마지막 원소(현재 n 이하의 가장 큰 피보나치 수)를 뺍니다.
- res를 1 증가시킵니다.
- 모든 반복이 끝나면 res를 반환합니다.
왜 그리디 알고리즘이 최적일까?
체켄도르프 정리(Zeckendorf's theorem)에 따르면 모든 양의 정수는 서로 인접하지 않은 피보나치 수들의 합으로 유일하게 표현할 수 있습니다. 매번 가능한 가장 큰 피보나치 수를 선택하면 필요한 항의 개수가 자연스럽게 최소화되므로, 이 그리디 방식이 항상 최소 개수를 보장합니다.
구현 예제
class Solution:
def solve(self, n):
res = 0
fibo = [1, 1]
while fibo[-1] <= n:
fibo.append(fibo[-1] + fibo[-2])
while n:
while fibo[-1] > n:
fibo.pop()
n -= fibo[-1]
res += 1
return res
ob = Solution()
n = 20
print(ob.solve(n))
입력
20
출력
3
복잡도 분석
피보나치 수열 생성에는 O(log n)개의 항만 필요하고, 각 단계에서 n은 최소 절반 이상 감소하므로 전체 시간 복잡도는 O(log n)입니다. 공간 복잡도 역시 피보나치 수열 저장에 O(log n)이 소요됩니다.