[Python] 프로그래머스 - 피보나치 수

Programmers 피보나치 수

풀이

def solution(n):
    a, b = 0, 1
    
    for _ in range(n):
        a, b = b, a + b
    
    return a % 1234567

F(2) = F(0) + F(1) = 0 + 1 = 1

F(3) = F(1) + F(2) = 1 + 1 = 2

F(4) = F(2) + F(3) = 1 + 2 = 3

F(5) = F(3) + F(4) = 2 + 3 = 5

• 위와 같은 식으로 더해지기 때문에 a, b = b, a+b로 표현할 수 있었다.

• 그리고 문제에서 n번째 피보나치수를 1234567로 나눈 나머지를 구하라고 하고 있기 때문에 return 값을 a%1234567로 설정하였다.

def solution(n):
    answer = 0
    
    answer = pibo(n)
    
    return answer

def pibo(k):
    if k == 0:
        return 0
    elif k == 1:
        return 1
    else:
        return pibo(k-1) + pibo(k-2)

처음에는 위와 같은 방식으로 풀이했는데, 같은 값을 계속 다시 계산하기 때문에 효율성 측면에서 실패했음