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

문제 정보

제목 : 피보나치 함수

번호 : 1003번

사용 언어 : Java

문제 링크

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

1003번: 피보나치 함수

 

시간 제한	메모리 제한
0.25 초 (추가 시간 없음)	128 MB

 

문제

다음 소스는 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이 나오면  전역변수 카운트를 +1하고 그외에는 fibonacci()함수 호출을 통해 구하는 방식입니다. 역시 이 방법은 시간초과가 뜨게 되었습니다.

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

public class Main {
   static int zero_count = 0;
   static int one_count = 0;
	
   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 T = Integer.parseInt(br.readLine());

      for(int i =0;i<T;i++)
      {
    	  int n = Integer.parseInt(br.readLine());
    	  fibonacci(n);
    	  bw.write(zero_count+" " +one_count +"\n");
    	  zero_count =0;
    	  one_count = 0;
      }

      bw.flush();
      bw.close();
      br.close();
   }

   static int fibonacci(int n) {
	   if (n==0) {
		   zero_count++;
		   return 0;
	   } else if (n==1) {
		   one_count++;
		   return 1;
	   } else {
		   return fibonacci(n-1) + fibonacci(n-2);
	   }
   }
}

 

다른 풀이

동적 프로그래밍을 통해 문제를 해결해야했습니다. 2차원 배열을 선언하여 행의 인덱스는 n이 되고 열의 인덱스는 각각 0과 1의 호출 횟수를 나타냈습니다. 그리고 dp[n][0]의 호출횟수는 fibonacci(n-1)[0] + fibonacci(n-2)[0]을 하여 효율적으로 0 호출 횟수를 카운트 하도록 했습니다. dp[n][1]의 호출횟수는 fibonacci(n-1)[1] + fibonacci(n-2)[1]을 하여 효율적으로 1 호출 횟수를 카운트 하도록 했습니다. 이 모든 과정이 끝나면 호출횟수를 각각 출력합니다.

 

코드

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

public class Main {
	static Integer[][] dp = new Integer[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));

		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
      
		int T = Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			int n = Integer.parseInt(br.readLine());
			
			bw.write(fibonacci(n)[0] + " " + fibonacci(n)[1]+"\n");
  
		}
		bw.flush();
	    bw.close();
	    br.close();
	}
   
	static Integer[] fibonacci(int n) {
		if(dp[n][0]==null || dp[n][1] == null) {
			dp[n][0] = fibonacci(n-1)[0] + fibonacci(n-2)[0];
			dp[n][1] = fibonacci(n-1)[1] + fibonacci(n-2)[1];
		}
		return dp[n];
	}
}