[백준] 피보나치 함수 [Java/ 자바]

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

코드: https://github.com/irerin07/AlgorithmStudyBaek/blob/master/src/baekjoon/baekjoon1003.java

 

package baekjoon;

import java.io.*;

public class baekjoon1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        int[] zeroCount = new int[41];
        int[] oneCount = new int[41];

        zeroCount[0] = 1;
        oneCount[0] = 0;
        zeroCount[1] = 0;
        oneCount[1] = 1;
        for (int j = 2; j < 41; j++) {
            zeroCount[j] = zeroCount[j-1] + zeroCount[j-2];
            oneCount[j] = oneCount[j-1] + oneCount[j-2];
        }

        for(int i = 0; i < num; i++){
            int a = Integer.parseInt(br.readLine());
            bw.write(zeroCount[a] + " " + oneCount[a] + "\n");
        }
        bw.flush();
        br.close();
        bw.close();

    }
}

문제를 잘못 이해해서 엄청 애먹은 문제

'fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.'

이 문장을 피보나치를 수행했을때 각 연산 결과값에 0과 1이 몇번 나오는지 구하라는 문제로 착각했다.

 

하지만 몇번을 도전해도 계속 오류가 나서 다른 사람들의 풀이를 보니

fibonacci(N)을 호출 했을 때 fibonacci(0)과 fibonacci(1)이 몇번씩 호출 되는지를 구하는 문제였다.

 

문제가 요구하는 사항을 이해하니 쉽게 풀린 문제.

 

40보다 작거나 같은 자연수가 주어지므로 크기 41의 두 배열, 

fibonacci(0)을 호출한 횟수를 저장하는 zeroCount,

fibonacci(1)을 호출한 횟수를 저장하는 oneCount 를 만든다.

 

N	0 호출	1 호출
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

 

위의 표를 보면 보이겠지만 N단계의 0과 1의 호출횟수는

N단계의 fibonaci(0)호출 횟수 = 0호출(N-1)+0호출(N-2)

N단계의 fibonaci(1)호출 횟수 = 1호출(N-1)+1호출(N-2)

이며

 

위와 같은 패턴을 바탕으로 코드를 짜서 문제를 해결할 수 있었다.