[백준] 그리디 알고리즘 - 피보나치 (9009번) #파이썬 #python

피보나치 (9009번)

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

문제

 

피보나치 수 ƒ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 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000. 

---

출력

 

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

---

예제 입력

 

4
100
200
12345
1003

---

예제 출력

 

3 8 89
1 55 144
1 34 377 987 10946
3 13 987

---

해답

 

f = [0, 1]
for i in range(2, 50):
    f.append(f[i-2] + f[i-1])

T = int(input())

for j in range(T):
    n = int(input())

    array = []

    while (n):
        for k in range(50):
            if (f[k] <= n):
                t = f[k]

        n = n - t
        array.append(t)
        array.sort()

    for l in array:
        print(l, end=' ')

---

풀이

 

먼저 구현에 필요한 피보나치 수들이 담긴 배열을 만듭니다.
문제에서 초기값이 0과 1이라고 하였으므로 초기값을 설정하고, append() 함수를 사용하여 피보나치 수들을 리스트에 삽입합니다.
피보나치 수열을 f에 저장한 뒤, 테스트 데이터 개수인 입력 T를 받습니다.
T만큼 테스트 케이스가 나오기 때문에, 반복문으로 range(T)만큼 범위를 설정해줍니다.
그리고 피보나치 수열로 나타낼 정수 n을 input으로 받습니다.
입력받은 수 n에 가장 근접한 피보나치 수를 찾고, 이를 array에 append() 함수로 추가해줍니다.
그 뒤에 n = n - t로 n 값을 바꾸어줍니다.
while 반복문이 끝나면 for 반복문을 통하여 array에 담긴 피보나치 수들을 출력해줍니다.

※ 이번 문제는 구현에 필요한 아이디어가 생각보다 쉽지 않아 다른 블로그를 참고하였습니다.
구현 아이디어에 대한 더 자세한 설명은 https://jeongminhee99.tistory.com/91에 나와있습니다.