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

피보나치 수열

• 피보나치 수열을 구현하여, n번째 인덱스에 위치하는 수를 1234567로 나눈 나머지를 반환하면 된다.
• 피보나치 수열은 0 1 1 2 3 5 와 같이 앞의 이웃한 두 수를 더한 수가 등장하는 수열이다.

테스트 케이스 절반 실패

• 해당 문제에서 요구하는 것처럼 아래와 같이 구현하고, 답을 1234567로 나눈 나머지를 반환하도록 하였다.

function solution(n) {
    const fibonazzi = [0, 1]
    // n번째 피보나치 수를 구하자.(n번째 인덱스임)
    
    while(fibonazzi.length <= n) {
    fibonazzi.push((fibonazzi[fibonazzi.length - 1] + fibonazzi[fibonazzi.length - 2]))    
    }
    return fibonazzi[fibonazzi.length - 1] % 1234567
}

그러나 테스트 케이스 7번부터 모조리 실패가 떴다. 원인이 뭐지..? 계속 고민하고 질문 게시판을 참고하던 중 아래와 같은 내용을 알게 되었다.

• 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다.
• 즉, 피보나치 수가 증가할수록 자료형이 담을 수 있는 범위를 훨씬 초과하게 되기 때문에, 1234567로 나눈 나머지를 반환하도록 안내해준 것이다.
• 즉 피보나치에 등장하는 수는 앞의 A + B를 더한 수이고, 문제에서는 이를 C로 나눈 나머지를 요구한다.
• 하지만 A + B는 정수 자료형이 담을 수 있는 범위를 초과하게 되기 때문에, 피보나치 수가 등장할 때마다 미리 C로 나눈 나머지로 넣는다. 해당 수는 작기 때문에 정수 자료형이 담을 수 있기 때문이다.

수정한 코드

function solution(n) {
    const fibonazzi = [0, 1]
    // n번째 피보나치 수를 구하자.(n번째 인덱스임)
    
    while(fibonazzi.length <= n) {
        fibonazzi.push((fibonazzi[fibonazzi.length - 1] + fibonazzi[fibonazzi.length - 2]) % 1234567)
    }
    
    
    return fibonazzi[fibonazzi.length - 1]
}