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

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

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

알고리즘

이번 문제는 피보나치 함수에서 0과 1이 출력되는 횟수를 출력하는 문제입니다.

재귀적으로 피보나치 함수 값을 구하는 코드가 있지만 재귀로 값을 구하게 된다면 시간초과가 나오게 됩니다.

따라서, 값의 규칙을 찾아 코드로 작성해야 하는 문제가 되겠습니다.

0의 개수를 zero, 1의 개수를 one 이라고 할 때, 차례대로 0과 1의 개수를 써보면

N = 0일 때, zero[0] = 1, one[0] = 0

N = 1일 때, zero[1] = 0, one[1] = 1

N = 2일 때, zero[2] = 1, one[2] = 1

N = 3일 때, zero[3] = 1, one[3] = 2

N = 4일 때, zero[4] = 2, one[4] = 3

N = 5일 때, zero[4] = 3, one[4] = 5

...

0과 1의 개수를 보면 규칙이 있습니다.

N이 0과 1일 때는 지정되어 있고, N=2 부터 보면

zero[2] = zero[1] + zero[0],       one[2] = one[1] + one[0]

zero[3] = zero[2] + zero[1],       one[3] = one[2] + one[1]

zero[4] = zero[3] + zero[2],       one[4] = one[3] + one[2]

zero[5] = zero[4] + zero[3],       one[5] = one[4] + one[3]

으로 zero[n] = zero[n-1] + zero[n-2]라는 것을 알 수 있습니다. (one도 마찬가지)

이 식을 사용하여 코드를 작성해 보도록 하겠습니다.

참고로, 이번 문제는 시간이 짧기 때문에 Scanner를 사용하던 분들은 BufferedReader로 사용해야 시간초과가 나지 않습니다.(=> Scanner보다 BufferedReader가 더 빠르다.)

---

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	StringBuilder sb = new StringBuilder();
		
		int[] zero = new int[41]; // N이 40까지
		int[] one = new int[41];
		zero[0] = one[1] = 1;
		zero[1] = one[0] = 0;
        
		int T = Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			for(int j = 2; j <= N; j++) {
            			//n = (n-1) + (n-2)
				zero[j] = zero[j-1] + zero[j-2]; 
				one[j] = one[j-1] + one[j-2];
			}
			sb.append(zero[N]).append(' ').append(one[N]).append('\n');
		}
		System.out.println(sb);
	}
}

---

이번 문제를 풀면서, 아직도 난 해석이 부족하다는 것을 다시 한 번 깨달았고, 좀 더 해석이 필요한 문제들을 풀어봐야할 것 같다.

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!