[프로그래머스] 피보나치 수 Java

나규태 2021. 9. 28. 01:05

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12945
레벨 : Level 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) =

programmers.co.kr

이 문제는 시간 초과가 발생할 수 있는 문제이다.

피보나치 수를 구하고나서 1234567의 나머지 값을 구한다면 시간 초과가 발생할 것이다.

또한 재귀함수로 피보나치 수를 구했을 때 배열보다 메모리를 많이 차지하여 시간 초과가 발생한다.

그래서 배열로 피보나치의 수식을 적용하고 각각의 값마다 1234567로 나머지를 구해서 로직을 구현하였다.

아래와 같이 소스를 공유합니다.

class Solution {
    public int solution(int n) {        
        
        int a = 0;
        int b = 1;
        
        for(int i = 0; i < n; i++) {
            int c = (a+b) % 1234567;
            a = b % 1234567;
            b = c % 1234567;
        }
        
        return a;
    }
}