백준 1003 피보나치 함수

1003번: 피보나치 함수Baekjoon Online Judge

Solution. bottom-up

• 14056 kb / 124 ms

• 시간 제한이 0.25초로 굉장히 엄격한 조건이었다.

• 접근방식

  • 구해야 하는 것은 f(0)과 f(1) 이 호출된 횟수이다.

  • 0부터 차례대로 0과 1이 호출된 횟수를 쌍으로 나열해보니 피보나치 함수처럼 이전의 두 결과값을 더한 것이 현재의 결과값을 나타내는 구조를 파악할 수 있었다.

    • f(3)에서 0이 호출된 횟수 = f(2)에서 0이 호출된 횟수 + f(1) 에서 0이 호출된 횟수

  • 따라서 피보나치 수열을 bottom-up 방식으로 구하도록 정의한 뒤, 매 연산의 결과를 배열에 저장하여 이전 연산 값을 참조할 수 있도록 하였다.

  • 그냥 피보나치수열보다 까다로웠던 점은, 0이 호출되는 횟수와 1이 호출되는 횟수 두 개를 각각 다른 배열에서 체크해야한다는 점이었다.

package practice.algorithm.dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * https://www.acmicpc.net/problem/1003
 * 14056 kb / 124 ms
 * 피보나치 함수
 * - 구해야하는 것 : f(0), f(1) 이 호출되는 각각 횟수
 * */
public class Bj1003 {

    private static int[] zero;
    private static int[] one;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (t != 0) {
            int n = Integer.parseInt(br.readLine());
            zero = new int[n+1];
            one = new int[n+1];

            fib(n);
            sb.append(zero[n]).append(" ").append(one[n]).append("\n");

            t--;
            Arrays.fill(zero, 0);
            Arrays.fill(one, 0);
        }

        System.out.println(sb);
    }

    private static void fib(int n) {
        zero[0] = 1;
        if (n == 0) return;

        one[1] = 1;
        if (n == 1) return;

        for (int i = 2; i <= n; i++) {
            zero[i] = zero[i-1] + zero[i-2];
            one[i] = one[i-1] + one[i-2];
        }
    }

    /**n - v    = (0 1)
     * 0 - 0    = 1 0
     * 1 - 1    = 0 1
     * 2 - 0+1  = 1 1
     * 3 = 2 + 1 = 0+1 + 1 = 1 2
     * 4 = 3+2 = 1 2 + 1 1 = 2 3
     * 1, 0
     * 0, 1
     * 1, 1
     * 1, 2
     * 2, 3
     * 3, 5
     * 5, 8
     * 8, 13
     * 13, 21
     * f(n) 까지의 0과 1의 호출 횟수 = f(n-1)까지의 횟수 + f(n-2)까지의 횟수
     * */
}