[백준] 피보나치 함수 JAVA

728x90

반응형

[백준] 피보나치 함수

---

접근

• dp(메모이제이션)

---

풀이

피보나치 함수의 0과 1이 반환되는 횟수를 구하는 문제이다. 문제에 나와있는 코드를 그대로 들고 가 count 변수를 할당해 직접 세어준다면 바로 시간초과가 나게 된다. 시간초과가 나지 않을려면 재귀나 탐색에서 사용되는 메모이제이션을 사용하여야 한다. 메모이제이션은 DP(Dynamic Programming) 동적 프로그래밍의 한 기법으로 이미 계산한 결과를 저장해 두고 다시 필요할 때 값을 꺼내어 재사용하는 기법이다.

private static final int MAX = 40;
private static final int[] countZero = new int[MAX + 1];
private static final int[] countOne = new int[MAX + 1];

현재 문제에서 입력의 최댓값이 40이므로 크기가 41인 0과 1의 횟수를 담을 배열을 선언해 준다. main 함수 내에서 선언해도 무방하다.

   countZero[0] = 1; countZero[1] = 0;
   countOne[0] = 0; countOne[1] = 1;

0번지와 1번지 값을 초기화해준다. 0의 경우 0일 경우 1을 리턴해야 하고 1일 경우 0을 리턴해야 한다. 1의 경우 0과 반대로 0일 경우 0을 리턴하고 1일 경우 1을 리턴해야 한다.

   for (int i = 2; i <= MAX; i++) {
      countZero[i] = countZero[i - 1] + countZero[i - 2];
      countOne[i] = countOne[i - 1] + countOne[i - 2];
   }

그리고 2번지부터 마지막 40번지까지 값을 미리 계산한다. 피보나치수열은 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)로

어쨌든 값을 구하는 과정에서 0과 1이 반환되는 횟수는 n-1항에서 반환되는 횟수 n-2항에서 반환되는 횟수를 더한 것과 같기 때문에 초기화 해준 값으로 bottom-up 방식으로 채워주면 된다.

   int n = Integer.parseInt(br.readLine());

   for (int i = 0; i < n; i++) {
      int num = Integer.parseInt(br.readLine());
      bw.write(Integer.toString(countZero[num]) + " " + Integer.toString(countOne[num]) + "\n");
   }

그리고 해당하는 번지의 값을 꺼내서 출력해주기만 하면 된다.

---

전체 코드

import java.io.*;

public class Main {
    private static final int MAX = 40;
    private static final int[] countZero = new int[MAX + 1];
    private static final int[] countOne = new int[MAX + 1];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        countZero[0] = 1; countZero[1] = 0;
        countOne[0] = 0; countOne[1] = 1;

        for (int i = 2; i <= MAX; i++) {
            countZero[i] = countZero[i - 1] + countZero[i - 2];
            countOne[i] = countOne[i - 1] + countOne[i - 2];
        }

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            bw.write(Integer.toString(countZero[num]) + " " + Integer.toString(countOne[num]) + "\n");
        }

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

문제에서 주어지는 피보나치수열 함수 코드를 그대로 가져와서 활용하려다 보면 꼬이는 문제이다.