1003 - 피보나치 함수

1003

피보나치 함수

• 진짜 개열받는 문제
• 답을 내는 자체는 어렵지 않은데... 메모리 초과와 시간 초과를 어떻게 해결하는지가 관건인 문제.
• 피보나치() 라는 함수가 있을 때, 피보나치(0) = 0 이고 피보나치(1) = 1 이며 이 둘을 제외한 수에 대해서는 피보나치(n) = 피보나치(n-1) + 피보나치(n-2)이다.
• 테스트 케이스 수 N이 입력되고, 그 후 N개의 수 가 입력될 때, 각 수에 대하여 피보나치를 실행했을 때 피보나치(0)과 피보나치(1)이 호출되는 횟수를 출력하라.

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

public class bj1003_0125 {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(bf.readLine()); // 케이스 수
		int[] N = new int[T]; // 케이스 별로 입력받을 배열

		int max = 0;

		for (int i = 0; i < T; i++) {
			N[i] = Integer.parseInt(bf.readLine());
			max = (N[i] > max) ? N[i] : max;
		}

		int[][] num = new int[max + 1][2];
		num[0][0] = 1;
		num[0][1] = 0;
		for (int i = 1; i <= max; i++) {
			num[i][0] = num[i - 1][1];
			num[i][1] = num[i - 1][1] + num[i - 1][0];
		}

		for (int i = 0; i < T; i++) {
			String str = Integer.toString(num[N[i]][0]) + " " + Integer.toString(num[N[i]][1]);
			bw.write(str + "\n");
		}
		bw.flush();
		bw.close();
	}

}

• 다시 말하지만 진짜 개 열받는 문제.
• 1트:
  • 쉬운 문제다 싶어서 그냥 굳이 피보나치 함수를 진짜 구현해서, 0과 1이 나오는 횟수를 하나하나 더해서 했더니, 시간초과가 나왔다.
• 2트:
  • 그래서 호락호락하진 않구나 싶어서, 직접 피보나치 함수를 구현하지 않고, 구현됐다 치고 함수 호출 횟수만 세서 했더니, 또 시간초과가 나왔다.
• 3트:
  • 질문 글에 대한 답들을 보니, 규칙이 있으니 그걸 배열에 먼저 넣어 놓고, 입력 받은 수에 따라 찾아서 꺼내주면 된다고 한다. 그래서 무슨 규칙일까 해서, 내가 짠 코드에 1 2 3 4 ~ 10 까지 입력해서 출력을 봤더니, 규칙이 있었다. 그 규칙대로 차례로 배열을 40까지 빌드하는 코드를 짰다. (각 수는 최대 40) 그리고 입력받으면 해당하는 수를 부르는 식으로 짜서 제출했다. 근데 또 시간초과가 나왔다.
• 4트:
  • 40까지 굳이 안해도 되는구나 싶어서, 입력 받은 수 중 최대값을 먼저 뽑아내고, 그 최대값까지만 규칙대로 0과 1의 개수를 다 계산하는 코드를 짰다. 그리고 입력받은 수에 해당하는 수를 부르는 코드를 제출했다. 근데 또 시간초과가 나왔다.
• 5트:
  • 그래서 Scanner와 sysout을 버리고 BufferedReader/Writer로 바꿨더니 됐다.
• 그냥 개열받음ㅎ;