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

피보나치수 문제 보기

접근 방식

일부 테스트 케이스 시간 초과 & 런타임 에러

처음에는 하기 코드와 같이 피보나치 재귀 함수를 생성한 후, solution 내부에서 값을 도출했다.
하지만 7번 테스트케이스 이후로 런타임에러와 시간초과가 났다!!!

def fibo(n):
    return fibo(n-1) + fibo(n-2) if n >= 2 else n

def solution(n):
    answer = fibo(n) % 1234567
    return answer

최종 코드

재귀로 풀면 안되는 문제인 것 같아서, 찾아본 결과
1. for문을 사용
2. 배열을 사용해 피보나치 수 관리
3. n번째 피보나치 수에 대한 값만을 찾는 것이 아니라, 모든 피보나치 수에 대해 1234567로 나눈 나머지를 구해줘야 함
이 3가지 포인트를 지켜야 정답을 맞출 수 있었다.

def solution(n):
    answer = [0,1] # fibo(0) = 0, fibo(1) = 1
    for i in range(2,n+1):
        answer.append((answer[i-1] + answer[i-2]) % 1234567)
    
    return answer[-1] # n번째 피보나치 수 % 1234567 리턴

배운점

▶️ 잠깨는 문제 ^.^ 피보나치는 당연히 재귀로만 할 줄 알았죠...