코딩테스트 연습 > 피보나치 수 - JAVA

 

 

문제

피보나치 수는 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	rerurn
3	2
5	5

 

 

코드

 

import java.util.*;

class Solution {
    public int solution(int n) {
        ArrayList<Integer> fibonacci = new ArrayList<>();
        fibonacci.add(0);
        fibonacci.add(1);
        for(int i = 2; i <= n; i++){
            fibonacci.add((fibonacci.get(i-2) + fibonacci.get(i-1))%1234567);
        }
        
        return fibonacci.get(n);
    }
}

 

 

풀이

 

피보나치 수는

워낙 유명해서 설명은 넘어가겠습니다.

 

이 문제의 주의점은

1. 피보나치 수를 1234567로 나눈 나머지 값을 반환해야 한다.

2. 시간 초과 문제를 잡아야 한다.

 

1. 관련 문제를 고려해야 하는 이유는

피보나치 수가 어느 순간부터

폭증한다는 점입니다.

 

그렇기에

int 형으로 담을 수 없는 수가 나올 수 있습니다.

그렇기에 저는 에초에 피보나치를 저장하는 List에

1234567로 나눈 나머지 값을 저장했습니다.

 

2. 관련해서는

처음에는 이 문제를 재귀함수로 구현했는데

시간 초과가 난다는 점이었습니다.

생각해보니 n이 최대 100,000인데

그만큼 재귀를 돌리는건

스택이 너무 많이 쌓이고,

함수를 왔다 갔다 하는데도 시간이 걸리고,

if 조건문도 있기 때문에 시간이 더 걸리기 때문이라고 생각합니다.

 

그래서 피보나치 수를 구하는 부분을 반복문으로 구현하니 해결됐습니다.

 

 

 

다음에 또 봐요