프로그래머스 알고리즘 #31 - 피보나치 수

<문제>

 

<풀이>

매~우 간단하게 생각한 문제였는데 생각하지 못한 함정이 있었다.

function solution(n) {
    var answer = [];
    answer[0] = 0;
    answer[1] = 1;
    for (let i=2; i<=n; i++){
        answer.push(answer[i-1]+answer[i-2]);
    }
    return answer[n]%1234567;
}

단순히 i-1번째와 i-2번째의 값을 더한 것을 push한 후

배열에서 뽑아와서 1234567로 나눈 나머지를 return했는데

이러면 케이스 6번까지만 통과하고 7번부터는 전부 실패한다.

 

 

문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다.

이러한 범위에 대한 이유때문에 그렇다는데.... 완전히 이해한것은 아니지만....

(자세한 설명이 보고싶다면 여기를 참고하세요)

 

암튼 어차피 1234567로 나눈 나머지를 return할 것이기 때문에

값을 저장할 때부터 1234567로 나눈 값을 넣어서 저장해버리면 문제가 해결된다.

function solution(n) {
    var answer = [];
    answer[0] = 0;
    answer[1] = 1;
    for (let i=2; i<=n; i++){
        answer.push((answer[i-1]+answer[i-2])%1234567);
    }
    return answer[n];
}