[Lv. 2] 피보나치 수

우선 처음엔 

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

코드를 위와 같이 작성했었다. 그런데?! 테케 7번부터 오류가 발생!

그래서 일단 코드를 아래와 같이 수정해보았다

일단 통과하고 싶어서 코드를 조금 수정해보았다

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

위와 같이 코드를 수정하니 모두 통과가 되었고 열심히 이유를 검색해봤더니

기억 저 너머에 잊혀지고 있던 모듈로 연산의 성질을 활용하면 되는 문제였다

(A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C

 

n번째 피보나치 수가 int 형에서 커버가 가능한 범위를 넘겨버릴 수 있기 때문에

위와 같은 성질을 활용하는 것이다.

 

1234567로 나누는 짓을 왜 하지???라는 의문이 해결됐다!