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

문제 링크: 1003번 제목

https://www.acmicpc.net/problem/1003

 

howManyCall(n)은 fibonacci(n)이 fibonacci(0) 과 fibonacci(1)을 몇 번 호출했는지를 return한다.

 

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

class Cnt {
    int cnt0;
    int cnt1;

    Cnt(int cnt0, int cnt1) {
        this.cnt0 = cnt0;
        this.cnt1 = cnt1;
    }

    public int[] getAll() {
        int[] arr = new int[2];
        arr[0] = cnt0; arr[1] = cnt1;
        return arr;
    }

    public String toString() {
        return Integer.toString(cnt0) + " " + Integer.toString(cnt1);
    }
}

public class Main {
    static Cnt[] cntArr;

    public static Cnt howManyCall(int n) {
        if (cntArr[n] != null) return cntArr[n];

        int[] arr1 = howManyCall(n-1).getAll();
        int[] arr2 = howManyCall(n-2).getAll();
        int cnt0 = arr1[0]+arr2[0];
        int cnt1 = arr1[1]+arr2[1];
        Cnt newCnt = new Cnt(cnt0, cnt1);
        cntArr[n] = newCnt;

        return newCnt;
    }

    public static void main(String[] args) throws IOException {
        cntArr = new Cnt[41];
        cntArr[0] = new Cnt(1, 0);
        cntArr[1] = new Cnt(0, 1);

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bf.readLine());
            sb.append(howManyCall(n).toString());
            sb.append('\n');
        }
        System.out.print(sb);
    }
}