[PS] 백준 1103/피보나치 함수 - 자바 풀이

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

 

정답 및 풀이

 

시간이 굉장히 빡빡한 상황에서 특정 값이 피보나치 수열의 루트 방향 트리 값인  0 혹은 1이 몇 번 사용되는지 구하는 문제이다. 일반적으로 피보나치는 재귀 함수를 이용해서 구현할 수 있다. 그러나 재귀 함수를 사용해서 문제를 풀 경우 시간 안에 정답을 구할 수 없다.

 

즉, 아래의 경우 시간 초과로 오답이다.

import java.util.*;

class Main{
	static int ansZero = 0;
	static int ansOne = 0;
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		
		for(int i = 0; i < t; i++) {
			fibonacci(sc.nextInt());
			System.out.println(ansZero + " " + ansOne);
			ansZero = 0;
			ansOne = 0;
		}
	}
	
	public static int fibonacci(int n) {
	    if (n == 0) {
	        ansZero++;
	        return 0;
	    } else if (n == 1) {
	    	ansOne++;
	        return 1;
	    } else {
	        return fibonacci(n-1) + fibonacci(n-2);
	    }
	}
}

 

정답

 

정답은 재귀보다 빠른 다이나믹 프로그래밍을 이용하여 피보나치에서 0과 1이 사용되는 경우의 수를 구하는 것이다.

import java.util.*;

class Main{
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int zero[] = new int[41];
		int one[] = new int[41];
		
		for(int i = 0; i < t; i++) {
			int n = sc.nextInt();
			zero[0] = 1;
			one[1] = 1;
			for(int j = 2; j <= n; j++) {
				zero[j] = zero[j-2] + zero[j-1];
				one[j] = one[j-2] + one[j-1];
			}
			System.out.println(zero[n] + " " + one[n]);
		}		
		
	}
}

 

zero 배열 : fibonacci(0)가 몇 번 호출되는지를 저장한다.

one 배열 : fibonacci(1)이 몇 번 호출되는지 저장한다

.

 

풀이 

우선 값이 0일때 fibonnaci(0)은 1이므로 zero[0] = 1;

마찬가지로 값이 1일때 fibonnaci(1)은 1이므로 one[1] = 1; 

 

값이 2일때는?

아래의 함수가 호출되어야한다.

fibonacci(1) + fibonacci(0)

 

값이 3일때는?

fibonacci(2) + fibonacci(1)

여기서 다시 fibonacci(2)는 fibonacci(1) + fibonacci(0)이다.

위에서 dp를 배열을 정의할 때 fibonacci(0) 는 zero[0] = 1이고 fibonacci(1)은 one[1] = 1이었다.

 

이를 일반화하면

zero[j] = zero[j-2] + zero[j-1];
one[j] = one[j-2] + one[j-1];

라는 식이 도출된다.

즉 3을 만들 때 쓰이는 0의 개수는 2를 만들때 쓰이는 0의 개수 + 1을 만들 때 쓰이는 0의 개수,

3을 만들 때 쓰이는 1의 개수는 2를 만들때 쓰이는 1의 개수 + 1을 만들 때 쓰이는 1의 개수이다.