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

문제

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

프로그래머스

 

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

 

제한 사항

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

 

 

정답

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        List<Integer> fibonacci = new ArrayList<>();
        fibonacci.add(0);
        fibonacci.add(1);
        
        for(int i = 0; i < n; i++) {
            fibonacci.add((fibonacci.get(i) + fibonacci.get(i+1)) % 1234567);
        }
        answer = fibonacci.get(n);
        return answer;
    }
}

 

 

 

풀이

        List<Integer> fibonacci = new ArrayList<>();
        fibonacci.add(0);
        fibonacci.add(1);

우선 fibonacci를 list로 선언하고 첫 번째 수와 두 번째 수를 넣었습니다.

 

        for(int i = 0; i < n; i++) {
            fibonacci.add((fibonacci.get(i) + fibonacci.get(i+1)) % 1234567);
        }

그 다음 for문을 돌면서 fibonacci에 넣습니다. 이때 문제에서 1234567로 나눈 나머지를 구하기 때문에 미리 나누어줍니다.

만약 나누지 않고 문제를 풀려면 int로는 제한 사항에 걸리기 때문에 자료형을 변경해서 문제를 풀어야합니다.

 

        answer = fibonacci.get(n);
        return answer;

마지막으로 n번째 숫자를 answer에 저장하여 문제를 풀었습니다.