Skip to main content

피보나치 수

문제 설명​

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

입출력 예​

nreturn
32
55

입출력 예 설명​

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

풀이​

첫 번째 풀이
def solution(n):
    fibo = [0] * 100001
    fibo[0], fibo[1] = 0, 1

    for i in range(2, n + 1):
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567

    return fibo[n]

문제를 읽어보면 F(0)과 F(1)은 각각 0과 1로 정해져 있습니다.

그리고 제한 조건을 읽어보면 n은 2 이상 100,000 이하이므로,

fibo 라는 리스트를 100,000개만큼 만들고 0번과 1번 index에 0과 1로 미리 초기화해놓고 나서 문제를 풀면 됩니다.

0번과 1번 index는 이미 초기화가 되어있기 때문에 2번부터 피보나치 수를 만들어 나가면 됩니다.

식은 문제 설명에서 F(n) = F(n-1) + F(n-2)라고 정의해줬기 때문에 그대로 적용하면 됩니다.

그리고 답은 n번째 피보나치 수를 1234567으로 나눈 나머지를 반환하라고 했기 때문에

피보나치 수를 만들 때부터 1234567으로 나눈 나머지를 저장하도록 했습니다.

그때 그때 1234567으로 나눈 나머지를 구해주지 않으면,

피보나치 수가 기하급수적으로 커지겠다고 생각했고, 큰 수 연산보다는 작은 수 연산이 빠를 것 같다고 생각했기 때문입니다.