[백준] 피보나치 : 9009번 - Python

https://www.acmicpc.net/problem/9009

9009번: 피보나치

 

 

 

문제를 풀면서 몰랐던 개념

 

[Python] for문을 이용한 피보나치 수열

: 피보나치 수열의 일반형은 fibo(n) = fibo(n-1) + fibo(n-2) 이다.

ex) fibo(1) = 1이라면,

    fibo(2) = fibo(1)

    fibo(3) = fibo(2) + fibo(1)

    fibo(4) = fibo(3) + fibo(2)

# 여러가지 방법으로 구현할 수 있지만 이번에는 for문을 이용한 구현 방식을 공부함 #

def fibo(n):
    f_list = []

    for i in range(0, n):
        if i < 2:	# fibo(1)과 fibo(2)는 값이 1이기 때문!
            f_list.append(1)
        else:
            f_list.append(f_list[i-1] + f_list[i-2])

    return f_list[n-1]	# 0번째 인덱스부터 시작했기 때문에 n-1번째 요소를 리턴!

print(fibo(5))   


>>> 5

 

 

 

문제의 접근 방법

 

- 피보나치 수열에 대한 개념 먼저 공부하고 접근하기

- 문제에서 주어진 n의 범위를 확인해서 피보나치 수열을 어디까지 출력해서 구현해야 할 지 범위 고민해보기

- 서로 다른 수를 사용해야 한다고 했으므로 f(0) = 0 과 f(1) = 1은 제외하고 f(2) = 1부터 첫 번째 값으로 고려하기

 

 

 

내가 막혔던 부분

 

- 피보나치 수열에 대한 개념 이해 부족

- 범위 지정

- 접근 아이디어

 

 

 

문제 풀이 방법

 

(1)

우선 피보나치 수열의 범위를 지정해야 하므로 0번째 값 0과 1번째 값 1이 들어있는 리스트 fib를 선언해준다.

대충 어림잡아 2부터 49번째 피보나치 수까지 출력해보았다. 

문제에서 테스트 데이터 n은 1,000,000,000 보다 작거나 같아야 한다고 했으므로 위의 결과를 보면 44번째 요소까지 사용 가능하다는 것을 알 수 있다.

따라서 피보나치 수의 범위를 44번째까지 설정하고 반복문을 돌려야 한다!

 

하지만,,,

 

문제에서는 서로 다른 피보나치 수들의 합으로 나타내야 한다고 명시되어있으므로 더할 때 의미가 없는 f(0) = 0과 f(1) = 1, f(2) = 1 로 같은 값을 가지고 있는 f(1)도 제해줘야 한다는 것을 알 수 있다.

따라서, 두 값을 빼고 3번째 값부터 1번째라고 생각하고 구현해야하므로 -2를 한 42번째 요소까지의 피보나치 수들을 가지고 계산해야 한다!!!

 

(2)

위에서 테스트 해봤던 거랑 똑같이 fib 리스트에 첫 번째, 두 번째 값인 1,2를 넣어준다.

반복문은 정해준 범위 미만까지 계산하는 개념이므로 42번째 요소까지의 수들을 추출하려면 2부터 43까지 범위의 for문을 돌려야 한다.

fib에 추가된 피보나치 수들을 출력해보면

>>>

[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 12139397, 2584, 4181, 6, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 57 514229, 832040, 02887, 9227465, 14930352, 24157817, 39088169, 63245986, 1023341, 39088169, 6324555, 165580141, 267914296, 433494437, 701408733]

다음과 같은 값이 나오는 것을 확인할 수 있다.

 

(3) 

최소 횟수를 구하려면 큰 값들부터 greedy하게 계산해주어야 하므로 리스트 fib를 내림차순 정렬한다.

 

(4)

테스트 케이스 T를 입력받아 그 개수만큼 n값을 입력받는 반복문을 만든다.

더해서 n을 만들 수 있는 최소수의 피보나치 수들을 저장할 리스트 result 선언해준다.

 

(5)

리스트 fib안에 있는 k값(변수)이 입력받은 정수 n보다 작거나 같으면 result에 추가한다. (만들 수 있는 가장 최대 값이 추가 될 것)

n에서 추가한 값만큼(k)을 빼준다.

위 과정을 n이 0이 될 때까지 반복해준다 (=n이 0이된다는 것은 추출한 숫자들을 더해서 n을 만들었다는 뜻)

 

(6)

내림차순 정렬돼있는 수들이기 때문에 큰 순서대로 result에 저장되었을 것이므로 조건문을 탈출하면 result를 정렬해준다.

 

(7)

가변인자를 사용해서 리스트 result 안에 있는 원소들을 차례대로 출력해준다!

 

 

 

소스코드

fib = [1, 2]    # 서로 다른 수를 써야하므로 1부터 저장 (0,1 제외)
# 풀이 (2)번 참고
for i in range(2, 43):  # 44번째까지 사용할 수 있으므로 -2해서 42번째 요소까지 사용가능!
    fib.append(fib[i-1] + fib[i-2])

fib.sort(reverse=True)  # 풀이 (3)번 참고
#print(fib)

T = int(input())

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

    for k in fib:   # 풀이 (5)번 참고
        if k <= n:
            result.append(k)
            n -= k
            
        result.sort()

    print(*result)