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로 바꿨더니 됐다.
- 그냥 개열받음ㅎ;
'PS - BOJ' 카테고리의 다른 글
1100, 1110, 1159 - 하얀 칸, 더하기 사이클, 농구 경기 (0) | 2022.01.27 |
---|---|
1026, 1037, 1085 - 보물, 약수, 직사각형에서 탈출 (0) | 2022.01.26 |
1094, 1015, 1057 - 막대기, 수열 정렬, 토너먼트 (0) | 2022.01.25 |
1034 - 램프 (0) | 2022.01.24 |
1138 - 한 줄로 서기, 1032 - 명령 프롬프트 (0) | 2022.01.23 |