0%

[백준/2747] 피보나치 수

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2747

Review

  • 본격 DP 들어가기 전에 한번 풀어본 문제.
  • 메모이제이션으로 풀었는데도 시간 초과가 떠서 당황하게 만들었던 문제다.
  • 알고 보니 내 코드에 문제가 있는 거였음. 역시 컴파일러는 거짓말을 안 한다… ㅜ
  • 일단 전역으로 배열 선언한 다음 메인 함수에서 초기화를 해준다.
  • 이때 입력값보다 1을 더해서 배열의 크기를 정해주어야 한다.
  • 예를 들어 0부터 10까지의 피보나치 수열을 구한다면, 배열의 크기는 0~10까지인 총 11이 되어야 하기 때문이다.
  • 그리고 피보나치 수열을 구하는 함수에서 배열에 값을 넣어주면 된다.
  • 나는 배열을 지역 변수로 선언했다가 시간 초과를 보았다… ㅡㅡ;;
  • 사실 1003 문제 풀고 싶었는데… 온갖 삽질로 시간 초과만 보다가 결국 풀지 못했다.
  • 1003은 다음 기회에… 꼭 플고 만다.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.*;

public class Main {
  static int[] memo;
  public static int fibonacci(int n) {
    

    if (n <= 1) {
      memo[n] = n;
      return n;
    } else if (memo[n] != 0) {
      return memo[n];
    } else {
      return memo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new int[input + 1];
    System.out.println(fibonacci(input));
  }
  
}