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

문제: https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

문제 설명

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• 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

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

입출력 예

nreturn

3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

---

정답

def solution(n):
    answer, prev = 1, 0
    for i in range(n - 1):
        answer, prev = answer + prev, answer
    return answer % 1234567

 

---

풀이

def solution(n):
    answer, prev = 1, 0
    for i in range(n - 1):
        answer, prev = answer + prev, answer
    return answer % 1234567

 피보나치 수를 구하는 문제입니다. 처음에는 피보나치 수의 일반항을 이용하려 했으나 코드가 복잡해져서 그냥 순서대로 연산해서 풀었는데 바로 통과되네요.

 

피보나치 수열의 일반항

 

피보나치 수열의 일반항을 이용해본 코드입니다.

import decimal


def solution(n):
    answer = decimal.Decimal(1 / 5 ** .5) * ((decimal.Decimal(decimal.Decimal((1 + 5 ** .5) / 2) ** n) - (decimal.Decimal((1 - 5 ** .5) / 2) ** n)))
    return round(answer) % 1234567

결과 정확성 테스트에서 실패가 발생합니다. 부동소수점을 표현하는 방식에서 오차가 생기는 것으로 추측합니다.