[Python] 1003번 : 피보나치 함수

 

문제 3줄 요약

1. 흔히 알던 피보나치 수열을 구현한다.

2. 기본 값인 0과 1을 몇 번 호출하는지 알아보고자 한다.

3. ex) 3 = 2+1 = 1+0+1 이므로 0은 1번 호출, 1은 2번 호출이다.

 

 

위의 피보나치 코드는 재귀 함수를 통해 실행 되며,

하향식 구조이다 보니 그대로 실행하면 시간 초과가 생긴다.

ex) 3 = 2+1 = 1+0+1

 

따라서 반복문을 통해 상향 구조로 코드를 작성,

한번 실행한 피보나치 값들은 리스트에 담아주어 재사용하는 방식으로

시간 초과를 해결하였다.

ex) 0=0, 1=1, 2=1+0, 3=1+0+1

 

from sys import stdin

T = int(stdin.readline())

def fibonacci(target):
	# 리스트의 첫 번째 값은 0의 호출수, 두 번째 값은 1의 호출수
    if (target == 0):
        return [1,0]
    elif (target == 1):
        return [0,1]
    else:
        return [L[target-1][0] + L[target-2][0], L[target-1][1] + L[target-2][1]]

for test_case in range(T):
    num = int(stdin.readline())
    # 값을 담을 리스트 생성
    L = []

    for i in range(num+1):
        L.append(fibonacci(i))

    print(L[-1][0], L[-1][1])

 

문자열 "1"과 "0"을 더하고 count를 하는 방법을 생각하였으나,

N이 최대인 40일 경우,

메모리 초과가 생기므로 호출 할 때마다 횟수를 더해주는 방식으로 하였다.

 

 

끝!