[알고리즘 PS] 백준 1003 피보나치 함수 자바 문제 풀이

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

문제

예제 입력 & 출력

 

해결법

해당 문제는 재귀 호출을 사용한 일반적인 피보나치 함수에서 0과 1이 각각 얼마나 출력되는지 확인하고 싶어하는 문제이다.

즉, 우리가 지난 재귀 호출 이론 시간에서 이야기 했던 0과 1의 중복에 대해서 생각해보자는 문제로 받아들일 수 있다.

 

근데 조금 생각을 해보아야 할 것이 시간 제한이 0.25초로 주어진다.

어떤 언어이던 간에 추가 시간은 주지 않는다고 한다.

그럼 사실상 우리의 알고리즘이 1초에 400만의 연산만 커버할 수 있다고 생각해야 한다.

피보나치 함수의 시간 복잡도는 지난 피보나치 수5에서 알아보았듯, 트리의 특성을 그대로 이어받아 2의 n제곱이 된다고 했다.

 

문제에서는 n이 40까지 주어질 수 있다고 했으니 2의 40제곱까지만 커버를 할 수 있다고 했을 때 2의 10 _ 4를 하면 1024 _ 4 를 수행하면 1조가 나온다..

 

그럼 절대로 재귀호출로 풀면 해당 문제는 통과하지 않으니 다른 방법을 생각해야 하는데, 이렇게 아주 많은 양의 데이터, 많은 양의 문제를 한 번에 해결하기 힘들 때 작은 여러 문제로 나누어서 푸는 동적 프로그래밍을 도입할 수 있다.

접근법

우리는 피보나치 함수를 직접 하나하나 다 구현하지 않고 각 재귀 호출의 특성을 파악해서 문제를 해결할 것이다.

 

다음과 같이 fibonacci 재귀 함수가 있다고 가정해보자.

int fibonacci(int n) {
  if(n == 0) {
    System.out.println("0");
    return 0;
  }else if(n ==0) {
    System.out.println("1");
    return 1;
  }else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

그럼 각각의 재귀 호출을 수행한 결과 0과 1이 출력되는 횟수는 다음과 같다.

 

         0의 출력   1의 출력
fibo(0) =   1       0
fibo(1) =   0       1
fibo(2) =   1       1

그럼 fibo(3)일 때 0과 1이 몇번 출력 될까?

fibo(3)은 fibo(1) + fibl(2) 이므로 각각의 횟수에서 출력된 1과 0을 서로 더하면 되지 않을까?

 

그렇다. 이것이 바로 핵심이다.

점화식으로 표현한다면, 다음과 같다.

 

fibo[n][0] = fibo[n-1][0] + fibo[n-2][0];
fibo[n][1] = fibo[n-1][1] + fibo[n-2][1];

이제 코드로 옮겨보자.

정답 코드

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int t = Integer.parseInt(br.readLine());
    int[][] fibo = new int[41][2];
    fibo[0][0] = 1; fibo[0][1] = 0;
    fibo[1][0] = 0; fibo[1][1] = 1;

    while(t-- > 0) {
      int n = Integer.parseInt(br.readLine());
      if(n > 1) {
        for(int i = 2; i <= n; i++){
          fibo[i][0] = fibo[i-1][0] + fibo[i-2][0];
          fibo[i][1] = fibo[i-1][1] + fibo[i-2][1];
        }
      }
      bw.write(fibo[n][0] + " " + fibo[n][1] + "\n");
    }

    bw.flush();
    bw.close();
  }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.