백준 2748번- '피보나치 수 2' (PYTHON 풀이)

문제:

 

N번째의 피보나치 수를 구하는 재귀 함수 유형의 문제이다.

피보나치 수에 대한 개념은 문제에 잘 나와있어 추가로 설명은 생략하겠다.

 

풀이:

import sys
N = int(sys.stdin.readline())

def fact(A):
    if A == 0:
        return 0
    elif A == 1:
        return 1
    return fact(A-1)+fact(A-2)

print(fact(N))

 

처음에 이렇게 풀었는데 자꾸 시간초과가 났다. pypy3로 냈는데도 시간초과가 발생하였다.

팩토리얼 푸는 것처럼 풀었더니 호출 횟수가 약 O(2^N)이 되어 이번 문제에서는 시간초과가 발생한 것 같다.

이를 해결하고자 반복문을 사용할건데 한번 계산한 건 추가 호출하지 않고 다시 쓰도록 해서 시간초과를 줄여보았다.

 

import sys
N = int(sys.stdin.readline())

def fact(A):
    if A == 0:
        return 0
    a, b = 0 , 1
    for i in range(1, A):
        a,b = b, a+b
    return b
print(fact(N))

 

거의 다 비슷한데, a,b를 0과 1로 선언하여 초기값을 넣어주고 반복문을 돌면서 a에 이전 a+b값(b), b에 새로운 a+b값을 더해주면서 b에는 최종적으로 피보나치 수열의 마지막 합계를 넣어주도록 한다.

이 로직을 따라서 가보면 결과적으로 b에는 앞서 말한 것처럼 우리가 구하고자 하는 피보나치 수열의 최종 값이 더해져 있을테니 이 값을 return 해주면 문제를 풀 수 있다.