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

문제 요약 설명

어떤 수 N이 입력으로 들어왔을 때, N번째 피보나치 수를 구하는 재귀함수 공식에서 n이 0이면 0을 출력하고 n이 1이면 1을 출력한다고 한다. 그렇다면 N번째 피보나치 수를 구할 때, 0과 1이 몇번 출력되는지를 구해야 한다.
예를 들어 3이 입력이라면 3은 fibo(2) + fibo(1)이고
fibo(2) = fibo(1) + fibo(0)이므로 1이 1번, 0이 1번 출력된다.
fibo(1)은 1이 1번 출력된다.
그래서 총 0은 1번, 1은 2번 출력되므로 "1 2"가 출력결과이다.

아이디어

1. 제한시간이 0.25초로 굉장히 짧기 때문에 재귀함수를 돌면서 0, 1이 나올때마다 카운팅하는 것은 안된다고 생각할 수 있었다.
2. fibo(n) = fibo(n-1) + fibo(n-2)라는 공식이 존재하기 때문에 fibo(n-1) 과 fibo(n-2)일 때 0과 1이 몇번 나오는지 알면 각각 더해주기만 하면 끝난다는 것을 알 수 있다. 즉 DP문제임을 바로 캐치할 수 있다.

풀이

1. ArrayList를 2차원 형태로 만든다.
   • 0번째 index : 0이 출력되는 갯수
   • 1번째 index : 1이 출력되는 갯수
2. ArrayList의 0번째와 1번째는 미리 삽입한다.
   -> 항상 고정된 값이기도 하고 fibo(n-2)를 구할때 오버플로우가 나지 않으려면 ArrayList에는 2개의 값이 꼭 들어가있어야한다.
3. k번째의 0과 1의 출력갯수는 다음과 같다
   • 0의 갯수 : ArrayList[k-1][0] + ArrayList[k-2][0]
   • 1의 갯수 : ArrayList[k-1][1] + ArrayList[k-2][1]
4. 2부터 N까지 2번의 방식으로 구한다음, ArrayList의 N번째 값을 출력한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int T = Integer.parseInt(input);

        int i = 0;
        ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>();

        //피보나치 0은 무조건 1, 0
        ArrayList<Integer> fibozero = new ArrayList<Integer>();
        fibozero.add(1);
        fibozero.add(0);

        //피보나치 1은 무조건 0, 1
        ArrayList<Integer> fiboone = new ArrayList<Integer>();
        fiboone.add(0);
        fiboone.add(1);

        for (i = 0; i < T; i++) {
            dp.clear();
            dp.add(fibozero);
            dp.add(fiboone);
            int N = Integer.parseInt(br.readLine());

            if (N == 0) {
                System.out.println(dp.get(0).get(0) + " " + dp.get(0).get(1));
            } else if(N == 1) {
                System.out.println(dp.get(1).get(0) + " " + dp.get(1).get(1));
            } else {
                int j;
                for (j = 2; j <= N;j ++) {
                    ArrayList<Integer> fibo = new ArrayList<Integer>();
                    fibo.add(dp.get(j-1).get(0) + dp.get(j-2).get(0));
                    fibo.add(dp.get(j-1).get(1) + dp.get(j-2).get(1));
                    dp.add(fibo);
                }
                System.out.println(dp.get(N).get(0) + " " + dp.get(N).get(1));
            }

        }
        br.close();
    }
}