[백준] 1003번 : 피보나치 함수(JAVA)

Dynamic Programming 이란 무엇인가....

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

1003번: 피보나치 함수

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

동적 계획법이란 Dynamic Programming 이라고도 하며

 

큰 문제를 작은 문제들로 나누어 해결하는 알고리즘이다.

 

이 문제를 풀고나서 다른 사람들이 푼 방법도 한번 비교해 봤는데

 

내 생각보다 많이 비슷해서 좀 놀란 문제이다.

 

나는 2차원 배열을 이용하여 문제를 해결하였으며

 

최대 40이 입력되므로 40개의 배열만 선언하고 미리 계산해 두는 방식으로 해결하였다.

 

import java.util.Scanner;

public class Question_1003 {
    static int[][] Fibo = new int[41][2];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int Test_Case = sc.nextInt();

        Fibo[0][0] = 1;
        Fibo[0][1] = 0;
        Fibo[1][0] = 0;
        Fibo[1][1] = 1;

        for(int i = 2; i < 41; i++) {
            Fibo[i][0] = Fibo[i-2][0] + Fibo[i-1][0];
            Fibo[i][1] = Fibo[i-2][1] + Fibo[i-1][1];
        }

        for(int i = 0; i < Test_Case; i++) {
            int A = sc.nextInt();
            System.out.println(Fibo[A][0] + " " + Fibo[A][1]);
        }
    }
}