[알고리즘] 프로그래머스 : 피보나치 수

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12945

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

 

내가 작성한 코드

처음에 이 문제를 접하고 무슨 이렇게 쉬운 문제가 다 있나 만만하게 보다가 큰코를 다칠 뻔했다. 프로그래머스에서 돌렸다가 에러가 떠서 무슨 일인가 싶어 이클립스에서 돌려봤더니 정수 범위를 초과하는 숫자가 나왔던 것... int를 long으로 변경해도 마찬가지였다.

이렇게 셀 수도 없는 큰 범위의 수를 어떻게 다뤄야할지 막막해하다가 1234567로 나눈 나머지라는 점에서 힌트를 얻었다. 문제를 출제한 사람도 이런 어마어마한 숫자가 나올 것임을 예상했을 것이고 그래서 1234567로 나눈 나머지를 int형 answer에 저장하여 반환하게 했을 것이다. 그렇다면 문제가 간단해진다. 피보나치 공식으로 i번째 요소의 값을 저장해가다가 그 값이 1234567보다 크거나 같다면 작아질 때까지 1234567을 빼주면 된다. 그 뒤 answer에 배열의 마지막 값을 저장해서 반환하면 끝! 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] fList = new int[n+1];
        fList[0] = 0;
        fList[1] = 1;
        for(int i=2; i<n+1; i++){
            fList[i] = fList[i-1] + fList[i-2];
            while(fList[i] >= 1234567) {
                fList[i] -= 1234567;
            }
        }
        answer = fList[n];
        return answer;
    }
}