[programmers/JAVA] 피보나치 수

AmeriKano·2023년 10월 13일

문제 링크

피보나치 수는 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번째 피보나치 수를 반환하는 문제인데, 나머지를 반환해야한다는 점이 다르다. 단순 피보나치 수는 dp를 이용하여 점화식을 세워 구하면 되는데, 매번 나머지를 계산해줘야 하므로 이전에도 이를 이용해 해결해본 적이 있는 모듈러 연산의 덧셈법칙을 활용해야 한다.
모듈러 연산의 덧셈법칙을 다시 정리해보면 다음과 같다.

(A + B) mod C = (A mod C + B mod C) mod C

소스 코드

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