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

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

1003번: 피보나치 함수

 

 

처음엔 단순하게 문제에서 주어진 피보나치 함수 긁어다가 0과 1 나올 때마다 관련 변수 1씩 증가시켜서 값을 구했는데 아니나다를까 시간 초과 남

근데 정리하다보니 예전에 풀었던 문제랑 비슷한 거 같아서 같은 풀이 사용하니 통과 됐다

아파트의 각 집마다 거주하는 사람 수 구하는 문제였던 거 같은데 몇 번인진 까먹었음

 

---

 

풀이

피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

문제를 좀 더 직관적으로 이해하기 위해 0번째 수도 수열에 포함하면 아래와 같음

0, 1, 1, 2, 3, 5, 8, 13, ...

n번째 피보나치 수는 위 배열의 n번 인덱스에 위치하는 것과 같다.

 

이 때 문제에서 fibonacci(n) 함수는 n번째 피보나치 수를 구하는데,

fibonacci(0)은 0을 1번 출력함 ==> 1 0

fibonacci(1)은 1을 1번 출력함 ==> 0 1

fibonacci(2)는 0을 1번, 1을 1번 출력함 ==> 1 1

fibonacci(3)은 0을 1번, 1을 2번 출력함 ==> 1 2

fibonacci(4)는 0을 2번, 1을 3번 출력함 ==> 2 3

 

fibonacci(n)은 fibonacci(n-1) + fibonacci(n-2)와 같다.

0과 1을 제외한 각 수의 0과 1의 개수 또한 바로 앞 두 수의 0과 1의 개수를 합친 것과 같다.

 

1. n을 입력 받은 후 n+1개의 행을 가지는 2차원 int 배열 생성
   1. n번째 수도 배열에 저장해야 하기 때문에 행의 개수는 n개보다 1개 더 많아야 함
2. 열에는 각 수의 0과 1의 개수 저장

 

코드

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

/*
 * 피보나치
 * 0, 1, 1, 2, 3, 5, 8, 13, ...
 * 4 => 피보나치(3)+피보나치(2) = 1 2 + 1 1 => 2 3
 */
public class Main {

	static int[][] createFibonacci(int n) {
		// n번째 수까지 배열에 저장할 수 있어야하므로 배열의 크기는 n+1
		int[][] fibonacci = new int[++n][2];
		fibonacci[0][0] = 1;
		fibonacci[0][1] = 0;
		
		// 입력값으로 0이 들어온 경우는 피하기 위해
		if (n > 1) {
			fibonacci[1][0] = 0;
			fibonacci[1][1] = 1;
		}
		
		// 각 수의 0과 1의 개수는 바로 앞 두 수의 0과 1의 개수를 합친 것과 같음
		for (int i=2; i<n; i++) {
			fibonacci[i][0] = fibonacci[i-1][0] + fibonacci[i-2][0];
			fibonacci[i][1] = fibonacci[i-1][1] + fibonacci[i-2][1];
		}
		
		return fibonacci;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int i=0; i<T; i++) {
			int n = Integer.parseInt(br.readLine());
			
			int[][] fibonacci = createFibonacci(n);
			sb.append(fibonacci[n][0]).append(' ').append(fibonacci[n][1]).append('\n');
		}
		
		System.out.println(sb);
	}

}