[백준 자바JAVA] 1003번 - 피보나치 함수

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

---

● 문제

피보나치 수열에서 호출되는 0과 1의 갯수를 구하면 되는 문제이다.

처음에는 원래 있던 피보나치 dp코드에 0과 1이 호출될때에 전역변수에 카운팅을 하는 방식으로 구성하였는데 이는 시간초과가 발생하였다.

생각을 해보니 피보나치 수열이 진행되면서 반복해서 사용되는경우가 발생하여 시간초과가 발생한 것 같았다.

예를 들어 fib(5)의 경우에는 0, 1, 2, 3을 반복해서 여러번 사용하므로 이는 다시 사용할 필요 없이 저장해 두었다가 사용하면 시간측면에서도 효율적이다.

 

그리고 0과 1이 나오는 패턴을 분석해보니

N	1	2	3	4	5	6	7	8	9
Fib(0)	1	0	1	1	2	3	5	8	13
Fib(1)	0	1	1	2	3	5	8	13	21

N에 대한 0호출 횟수 = N - 1의 1 호출 횟수

N에 대한 1호출 횟수 = N - 1의 0 호출 횟수 + 1 호출 횟수

라는 공식이 발견된다.

나는 위의 반복을 통하여 코드를 구성해 보았다.

---

● 코드

import java.io.*;

public class Main {

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

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            fibonacci(N);
        }
    }

    public static void fibonacci(int n) {
        int first = 1;
        int second = 0;
        int tmp = 1;

        for(int i = 0; i < n; i++) {
            tmp = first;
            first = second;
            second = tmp + second;
        }

        System.out.println(first + " " + second);
    }

}