[연습문제] 피보나치 수 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

[문제 간단 요약]

1. 피보나치 수를 구현하는 문제

2. 피보나치 수의 1234567로 나눈 값을 구하기

[문제 해결 방안]

1. 피보나치 수 f(0)과 f(1)을 미리 지정

2. 이후의 값을 앞의 2개와 합산해서 구해지도록 하

 

[문제 해결 코드 - python]

def solution(n):
    dp=[0] * 100001
    dp[0]=0
    dp[1]=1
    for i in range(2,n+1):
        dp[i] = dp[i-2]+dp[i-1]   

    return dp[n] % 1234567

 

[문제 해결 코드 - javascript]

function solution(n) {
    const dp = Array(n+1).fill(0)
    dp[0] = 0
    dp[1] = 1
    for (let i=2; i<=n; i++) {
        dp[i] = (dp[i-2] + dp[i-1]) % 1234567
    }
    return dp[n];
}

 

- 테스트 케이스 7~14번 문제 실패 원인 : 피보나치 수의 크기가 너무 커져 자료형의 범위를 넘어 오버플로우 발생

- (A + B) % C == (A % C + B % C) % C라는 수학적 성질을 이용하여 1234567보다 작은 수를 유지 하도록 만듬