[백준 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);
​​​​}
}