피보나치 수

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

핵심 아이디어
(1) 문제를 풀다보면 정답을 일정 수로 나눈 나머지의 값을 출력하라는 문제가 나온다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

이러한 문제는 보통 java를 기준으로 int형의 범위를 넘는 값일 확률이 굉장히 높다. 즉, 로직은 맞지만 자료형의 범위 때문에 오버플로우가 발생할 가능성이 굉장히 높다. 이럴때는 모듈러 연산 분배법칙을 사용하면 된다.

모듈러 연산 분배법칙

(A + B) % p = ((A % p) + (B % p)) % p
(A B) % p = ((A % p) (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

위와 같은 공식이다!

(2) 나는 피보나치 유형을 보면 동적프로그래밍인 dp를 사용한다. dp는 값을 누적시키기 때문에 시간복잡도를 줄이는데 굉장히 효율적이다.(계산한 값을 또 계산하지 않아도 된다.)

public int solution(int n) {

        int answer = 0;
        
        int[] dp = new int[100001];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <=100_000; i++) { // 모듈러 연산
            dp[i] = dp[i-1]%1234567 + dp[i-2]%1234567;
        }

        answer = dp[n]%1234567;

        return answer;
    }