피보나치 수열 문제

문제 주제

숫자 n이 주어지고, 1234567 로 나눈 나머지를 리턴하는 피보나치 함수를 작성해라

 

 

문제 해결 방법

1. 재귀는 시간 초과

2. 반복문을 사용하되 각 요소 값마다 123456 나머지를 구해서 배열에 넣어줌

3. 입력받은 n의 인덱스에 위치하는 배열 요소 값을 반환

 

 

public class 피보나치수열 {

    /*
    - 문제 : 숫자 n이 주어지고, 그 수를 1234567 로 나눈 나머지를 리턴하는 함수를 작성해라

    * */
    public static void main(String[] args) {
        System.out.println(solution(3));
    }

    public static int solution(int n) {
        int[] answer = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if(i==0) answer[i] = 0;
            else if(i==1) answer[i] = 1;
            else{
                int sum = answer[i-2] + answer[i-1];
                answer[i] = sum % 1234567;
            }
        }

        return answer[n];
    }

}