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

문제

다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

 

---

문제 접근 방법

피보나치수열은 재귀 호출 함수로 쉽게 구현이 가능하다. 심지어 문제에서 C++ 이긴 하지만 피보나치 함수를 제공해 줬다. 그러나, 문제에서 준 함수 그대로 코드에 가져다 쓰면 시간 초과 에러가 난다. 그렇다면 시간을 줄여야 하는데, 가장 먼저 생각해 볼 수 있는 방법이 반복된 연산을 없애는 것이다. 피보나치수열의 경우 재귀 형식으로 함수가 작성되어 있으면 결국 if문에 걸려야 다시 회귀를 하면서 값을 리턴하는 방식이다. 그렇다면 이때, 최초 1회만 계산을 하고 계산을 한 내용을 배열에 저장해두면 재귀 호출을 했을 때 반복된 연산을 하지 않고 이전에 계산한 내용을 호출만 하면 되므로 훨씬 시간이 단축된다. 말로는 왜 이게 시간이 많이 단축되는지 감이 안 올 분들을 위해 예시를 들어보겠다.

 

먼저 3번째 피보나치 수를 구해보겠다.

그렇다면 다음과 같은 과정이 일어날 것이다.

	- - - - - - - - - - - - - - - - - - - 코드 흐름 - - - - - - - - - - - - - - - - - - - >
f i b o n a c c i 실 행 과 정	fibonacci(3)
		fibonacci(2)			fibonacci(1)
			fibonacci(1)	fibonacci(0)
			return 1;	return 0;
		return fibonacci(1) + fibonacci(0);			return 1;
	return fibonacci(2) + fibonacci(1);

이제 두 번째로 4번째 피보나치 수를 구해보겠다.

먼저 문제에서 주어진 함수로 진행을 하면 다음과 같은 과정이 일어난다.

	- - - - - - - - - - - - - - - - - - - 코드 흐름 - - - - - - - - - - - - - - - - - - - >
f i b o n a c c i 실 행 과 정	fibonacci(4)
		fibonacci(3)					fibonacci(2)
			fibonacci(2)			fibonacci(1)		fibonacci(1)	fibonacci(0)
				fibonacci(1)	fibonacci(0)
				return 1;	return 0;
			return fibonacci(1) + fibonacci(0);			return fibonacci(1) + fibonacci(0);		return 1;	return 0;
		return fibonacci(2) + fibonacci(1);					return fibonacci(2) + fibonacci(1);
	return fibonacci(3) + fibonacci(2);

그러나 3번째 피보나치 수를 구했을 때 했던 연산을 배열에 저장해 두면 다음과 같은 과정이 일어난다.

	- - - - - - - - - - - - - - - - - - - 코드 흐름 - - - - - - - - - - - - - - - - - - - >
f i b o n a c c i 실 행 과 정	fibonacci(4)
		fibonacci(3)	fibonacci(2)
		return fibo[3];	return fibo[2];
	return fibonacci(3) + fibonacci(2);

두 버전의 과정이 한눈에 봐도 확연히 차이가 나는 것을 볼 수 있다.

따라서 fibonacci 함수의 코드는 문제에서 주어진 알고리즘을 토대로 불필요하게 반복되는 연산을 하지 않는 코드(배열에 연산 결과 저장하기)로 작성해주면 이번 문제를 시간 초과 없이 해결할 수 있을 것이다.

그 코드는 다음과 같다.

// int fibo[] = new fibo[구하려는 n보다 큰 수];
// fibo[0] = 0;
// fibo[1] = 1;
// 위 두 값은 fibo배열 안에 들어있어야 하고 fibonacci함수가 fibo함수를 호출 할 수 있어야 한다.
static int fibonacci(int n) {
    if(n == 0)
        return fibo[0];
    else if(n == 1)
        return fibo[1];
    else if(fibo[n] == 0) { // 아직 연산되지 않은 n번째 피보나치 수
        StringBuilder sb = new StringBuilder();
        sb.append(fibonacci(n-1));
        sb.append(fibonacci(n-2));
        fibo[n] = Integer.parseInt(String.valueOf(sb));
    }
    return fibo[n];
}

그러나 문제에서는 단순히 n번째 피보나치 수를 구하라는 것이 아닌, n번째 피보나치 수의 0의 개수와 1의 개수를 구하라는 것이므로 다음과 같이 함수를 작성해주면 된다.

static int[] fibonacci(int n) {
    if(n == 0)
        fibo[0][0] = 1;
    else if(n == 1)
        fibo[1][1] = 1;
    else if(fibo[n][0] == 0 && fibo[n][1] == 0) { // 아직 계산되지 않은 n번째 피보나치 수
        fibo[n][0] = fibonacci(n-1)[0] + fibonacci(n-2)[0];
        fibo[n][1] = fibonacci(n-1)[1] + fibonacci(n-2)[1];
    }
    return fibo[n];
}

---

JAVA 코드 풀이

import java.io.*;

public class Main {
    static int cnt0, cnt1;
    static int fibo[][] = new int[41][2];
    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 tC = Integer.parseInt(br.readLine());
        int n;
        for(int i=0; i<tC; i++){
            cnt0 = 0;
            cnt1 = 0;
            n = Integer.parseInt(br.readLine());
            fibonacci(n);
            bw.write(fibo[n][0]+" "+fibo[n][1]+"\n");
        }
        bw.close();
    }
    static int[] fibonacci(int n) {
        if(n == 0)
            fibo[0][0] = 1;
        else if(n == 1)
            fibo[1][1] = 1;
        else if(fibo[n][0] == 0 && fibo[n][1] == 0) {
            fibo[n][0] = fibonacci(n-1)[0] + fibonacci(n-2)[0];
            fibo[n][1] = fibonacci(n-1)[1] + fibonacci(n-2)[1];
        }
        return fibo[n];
    }
}

코드 실행 결과

---

후기

이번 문제는 시간제한이 빡세게 걸린 문제이다. 이 말인 즉슨 단순 재귀만으로는 해결이 되지 않고, 같은 연산을 반복하지 않는 알고리즘을 작성하라는 문제였다. 이 문제를 풀면서 효율적인 측면에서 다시 생각해 볼 수 있는 계기가 되었다.

---

문제 원본

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