Programmers - 피보나치 수 (Java) (Lv.2)

*모든 풀이 코드는 직접 작성하였습니다.

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

문제 풀이

수들을 계속 업데이트 해주고 연산만 해주면 된다. 단, 피보나치 수열 특성상 그 값들이 급격히 커지므로, 오버플로우가 일어나지 않게 신경을 써야 한다.

나머지를 계산할 때, 분배법칙이 적용되기 때문에, n번째 피보나치 수열에서 1234567을 나눈 나머지를 구한 값과, 연산을 계속 하며 1234567을 나눈 나머지값을 사용해 피보나치 수열을 이어 가도 결과값은 같다. 이렇게 하면 오버플로우를 피할 수 있다.

풀이 코드

class Solution {
    public int solution(int n) {
        int j = 0;
        int k = 1;
        int sum = 0;
        for(int i = 2; i <= n; i++){
            //바로 나머지 연산
            sum = (j + k) % 1234567;
            j = k;
            k = sum;
        }
        return sum;
    }
}