[코딩테스트 챌린지] 백준 2748 피보나치 수 2 (java)

문제

https://www.acmicpc.net/problem/2748

 

 

문제 탐색하기

1. 동적 계획법이란

Dynamic Programing, 줄여서 DP라고 하며, DP 알고리즘 기법은 이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용할 수 있도록 하는 방법입니다. 

동적계획법은 크게 재귀(Top-Down) 방식, 반복문(Bottom-Up) 방식이 있습니다. 이번 문제는 Bottom-Up방식을 사용해보려 합니다. 

 

Bottom-Up 방식은 하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제의 값을 활용하여 상위 문제를 해결해나가는 방식으로 DP의 전형적인 형태입니다. 이전 피보나치 수를 통해서 다음 피보나치 수를 계산해나가는 형태로 문제를 풀면 될 것 같습니다.

 

 

2. 시간복잡도

피보나치 수를 나열해보았을 때 0번째 수와 1번째 수를 제외하고 2번째 수부터는 바로 앞 두 개의 피보나치 수의 합이 되는 것이 반복됩니다.

배열에 피보나치 수를 저장하고 이를 통해서 계산하는 방식이기에 시간복잡도는 O(n)이며, n이 최대 90까지 입력을 받을 수 있기때문에 시간 내에 충분히 연산가능할 것이라 생각합니다.

 

코드 설계하기

1. 숫자 N 입력 (자연수 , 1<= n <= 90)
2. 피보나치 수는 0번째부터 나열하므로 배열은 N+1의 원소를 저장할 수 있도록 선언
3. 피보나치 수 배열에 입력
   1. 0번째와 1번째 피보나치 수는 초기값 입력
   2. 2번째 피보나치 수 부터 바로 앞 두 피보나치 수를 합하는 연산을 진행
4. N번째 피보나치 수를 배열에서 찾아서 출력

 

정답코드

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

public class Fibonacci {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 1. 숫자 N 입력 (자연수, 1 <= N <= 90)
        int N = Integer.parseInt(reader.readLine());

        // 4. N번째 피보나치 수 출력
        System.out.println(function(N));
    }


    private static long function(int N){
        if(N <= 1) return N;

        // 2. N = 3일 경우 0, 1, 2, 3 총 4개의 피보나치 수가 저장되어야하므로 배열은 N+1로 생성
        long[] fibonacci = new long[N+1];
        fibonacci[0] = 0;
        fibonacci[1] = 1;

        // 3. 피보나치 수 배열에 입력
        for(int i=2; i<=N; i++){
            // # 2번째 피보나치 수부터 아래와 같은 연산을 진행해서 저장
            fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];
        }

        return fibonacci[N];
    }
}