[코딩테스트] 피보나치 수

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

정직하게 풀면 되는 문제지만 n의 단위가 오르면 피보나치 수의 크기 역시 기하급수적으로 오르는 것을 감안해야 한다.
처음에 그냥 풀었다가 오버플로우 탓에 테스트케이스에서 오류가 났다.
어차피 나머지만 구하면 되는 것이므로 매 sum값에 1234567의 나머지를 입력한 뒤 결과를 내게끔 하니 해결되었다.

풀이

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