0%

[백준/1003] 피보나치 함수

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1003

Review

  • 9월에 몇 번 풀었다 실패한 문제다. 며칠 전까지 계속 틀려서 총 8번을 틀렸는데, 대부분이 시간 초과였다.
  • 예전에는 재귀로 풀어도 AC를 받은 것 같은데 지금은 안 되는 걸 보니 시간 제한이 바뀌었나 봄. 그래서 메모이제이션으로 풀었다.
  • 처음에는 그냥 단순하게 전역으로 zero, one 변수를 선언하고 0일 때, 1일 때 각각 zero, one 값을 증가하는 방식으로 풀었다. 당연 틀림 ㅋㅋ. 이렇게 하면 안 된다. 내가 문제 제대로 이해 못하기도 했고… 아무튼 여기서 삽질 진짜 많이 했다.
  • example
  • fibonacci(5)는 fibonacci(4) + fibonacci(3)의 값으로 구할 수 있다. fibonacci(4)의 0과 1의 개수는 각각 2 3, fibonacci(3)의 0과 1의 개수는 1 2다. 따라서 fibonacci(5)는 그 둘을 더한 3 5가 된다. 참고로 fibonacci(4) = 3, fibonacci(5) = 5이다.
  • 결과적으로 0의 개수는 fibonacci(n-1), 1의 개수는 fibonacci(n)일 때 구할 수 있다.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  static int[] memo;

  public static int fibonacci(int n) {
    if (n == 0) {
      memo[0] = 0;
      return 0;
    } else if (n == 1) {
      memo[1] = 1;
      return 1;
    } 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 in = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(in.readLine());
    for(int i = 0; i < T; i++) {
      int N = Integer.parseInt(in.readLine());
      memo = new int[N + 1];

      if(N == 0) {
        System.out.println(1 + " " +0);
      } else if(N == 1) {
        System.out.println(0 + " " +1);
      } else {
        fibonacci(N);
        System.out.println(fibonacci(N-1) + " " + fibonacci(N));
      }
    }
  }
}