[BOJ][B2]피보나치 수 - 2747

https://www.acmicpc.net/status?user_id=idleh&problem_id=2747&from_mine=1

문제 전문은 링크 참조

문제가공

n번째에 해당하는 피보나치 수를 출력하자.

코드작성

아래와 같이 피보나치 함수를 그대로 적용하면 시간초과 발생 (O(2^n)

def fibbo(n):
    if n ==0:
        return 0
    elif n==1:
        return 1
    else:
        return fibbo(n-1) + fibbo(n-2)
print(fibbo(int(input())))

아래처럼 최종 합을 이용해서 반복 처리 하는 구조로 변경한다.

def fibbo2(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a    
    
print(fibbo2(int(input())))