[JAVA] 백준 1003 : 피보나치 함수

 

문제에 주어진 피보나치 함수를 사용하여 0과 1이 출력될 때마다 값을 세는 방법도 있지만, 그렇게 구현하면 시간 초과가 나온다.

그래서 어떻게 해야 할까 고민하다가 N에 따라 0과 1이 출력되는 횟수를 써보았다.

N	0	1
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

그리고 규칙을 찾았다.

N이 주어졌을 때, 0과 1이 출력되는 횟수는 n-2번째 횟수와 n-1번째의 횟수를 더한 값이다.

그래서 이와 같이 구현했다.

 

1. N은 0부터 40까지이므로 크기 41인 arr_0, arr_1 배열을 만든다.

2. 각 배열의 0번째 값과 1번째 값을 지정해준다.

3. n번째 횟수는 n-2번째 횟수와 n-1번째 횟수를 더한 값이라는 것을 이용하여 배열에 값을 채워준다.

4. 들어오는 값을 받아 StringBuilder에 추가하여 출력한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		int[] arr_0 = new int[41]; // 0이 출력되는 횟수
		int[] arr_1 = new int[41]; // 1이 출력되는 횟수
		
		arr_0[0] = 1;
		arr_0[1] = 0;
		arr_1[0] = 0;
		arr_1[1] = 1;
		
		for (int i = 2; i < 41; i++) {
			arr_0[i] = arr_0[i - 2] + arr_0[i - 1];
			arr_1[i] = arr_1[i - 2] + arr_1[i - 1];
		}
		for (int i = 0; i < num; i++) {
			int n = Integer.parseInt(br.readLine());
			sb.append(arr_0[n] + " " + arr_1[n] + "\n");
		}
		
		System.out.println(sb);
	}
}