[JAVA] BOJ 1003번 피보나치 함수

 

단순 피보나치수열을 구하는 것은 백 트레킹으로 쉽게 구할 수 있지만 동적 계획법 문제는 메모이제이션을 추가로 구현해야 한다. 이 문제는 피보나치수열을 구하는 동적 계획법 문제와 비슷하지만 출력하는 형식이 다르다. 

 

각 테스트케이스에 대해 N이 0이 되는 횟수와 1이 되는 횟수를 구해야 하는데 피보나치수열은 F(N) = F(N-1) + F(N-2) 의 점화식을 따르고, 피보나치수열의 초기값 두 개인 0, 1을 호출하는 횟수 또한 이 점화식을 따라 증가하는 형태를 띤다. 예제에서도 볼 수 있듯 F(2)_zero = F(1)_zero + (F0)_zero, F(2)_one = F(1)_one + F(2)_one을 만족하여 [1 1]을 출력할 것이고 F(3) 또한 이를 만족하여 [1 2]를 출력한다.  

*F(N)_zero : N번째 피보나치 수열을 구하기 위한 로직에서 0을 호출하는 횟수

 

따라서 다음과 같이 두 개의 메서드를 구현했다. 

static int zero_fib(int N) {
  if(N==0) return 1;
  else if(N==1) return 0;
  if(zero_cnt[N] !=0) return zero_cnt[N];
  return zero_cnt[N] = zero_fib(N-1) + zero_fib(N-2);
}
static int one_fib(int N) {
    if(N==1) return 1;
    else if(N==0) return 0;
    if(one_cnt[N] !=0) return one_cnt[N];
    return one_cnt[N] = one_fib(N-1) + one_fib(N-2);
}

이 방법이 효율적인가 하면...그렇다 라고 답할 순 없지만 이게 최선의 방법이었다...(아직 실력이 부족하여ㅠ) 

zero_fib 메서드에서는 N이 0을 호출할 때만 return 1을 해주어 호출 횟수를 피보나치수열로 가져갔다. one_fib 메서드에서는 반대로 N이 1을 호출할 때만 return 1을 해주었다. 

 

public class Main {
	public static int[] zero_cnt;
	public static int[] one_cnt;
	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 N = Integer.parseInt(br.readLine());
		zero_cnt = new int[41];
		one_cnt = new int[41];
		StringTokenizer st;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			bw.write(zero_fib(n)+ " " + one_fib(n));
			bw.newLine();
		}
		bw.flush();
		bw.close();
		
	}
	static int zero_fib(int N) {
		if(N==0) return 1;
		if(N==1) return 0;
		if(zero_cnt[N] !=0) return zero_cnt[N];
		return zero_cnt[N] = zero_fib(N-1) + zero_fib(N-2);
	}
	static int one_fib(int N) {
		if(N==1) return 1;
		if(N==0) return 0;
		if(one_cnt[N] !=0) return one_cnt[N];
		return one_cnt[N] = one_fib(N-1) + one_fib(N-2);
	}
}

 

이번에도 역시 시간 단축을 위해 BufferedReader 와 BufferedWriter 를 사용하였고 0을 호출한 횟수를 저장해주는 배열 zero_cnt와 1을 호출한 횟수를 저장해주는 배열 one_cnt를 41의 크기로 선언하였다. (N이 40보다 작거나 같은 자연수이기 때문).  자바는 배열을 선언하면 선언한 사이즈만큼 0으로 채운 배열을 만들어주기 때문에 one_cnt [N]가 0인지 아닌지에 따라 방문 여부를 체크하였다. 처음에는 재귀 함수를 두 개나 만들어서 시간 초과에 걸릴 줄 알았지만 다행히도 통과할 수 있었다.