백준 알고리즘 15624 피보나치 수 7

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

 

풀이

풀이 방법은 문제에서 제공해준 Fn = Fn-1 + Fn-2 (n ≥ 2) 을 사용하면 편리하게 풀 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Quiz_15624 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());

        long[] arr = new long[count+1];
        if(count > 0) arr[1] = 1;

        for(int i = 2; i <= count; i++ ) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
        }
        System.out.println(arr[count]);
    }
}

1. 먼저 1,000,000 이하의 숫자를 입력 받는 count를 만든다.

2. 입력 받는 숫자에 1을 더하여 배열에 크기에 넣는다.

3. 배열의 0번째는 0(값을 넣지 않아도 0), 1번째는 1로 값을 넣어준다.

4. 배열의 2번째 인덱스부터 입력받은 count까지 반복문을 돌린다.

5. 배열의 값에 Fn = Fn-1 + Fn-2 (n ≥ 2) 공식을 사용하여 값을 넣어준다.

6. Fn 값에 1,000,000,007으로 나머지를 구한다. ( 6번 과정을 하지 않으면 숫자가 너무 커져 int 크기를 벗어난다.)

 

문제는 매우 간단했다. 하지만 문제를 풀면서 궁금증이 생겼다.

배열과 리스트중 어떤것이 효율적인지 알아보고 싶었다.

그래서 배열을 사용하지않고 자료구조인 list를 사용해봤다.

 

import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.ArrayList;
        import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());

        int sum = 0;

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i <= count; i++ ) {
            if(i == 0 ) list.add(0);
            if(i == 1) list.add(1);

            if(i >= 2) {
                sum = list.get(i - 1) + list.get(i -  2) ;
                list.add(sum % 1000000007);
            }
        }

        System.out.println(list.get(list.size() - 1));

    }
}

 

배열과 리스트의 성능을 배교해보았다.

 

첫번째는 List를 사용한 결과

두번째는 Array 배열을 사용한 결과이다.

List보단 배열이 메모리와 시간 모두 효율이 좋았다.

 

배열과 리스트의 차이 알기

https://jy-tblog.tistory.com/38