백준 1003 피보나치 함수 (Java)

1. 문제 링크

1003번: 피보나치 함수

 

2. 문제 및 입출력예제

 

3. 문제 풀이

N번째 피보나치 수를 구하는 과정에서 1번째 피보나치 수와 0번째 피보나치 수가 몇 번 호출되었는지를 구하는 문제이다.

초반인 0번 피보나치와 1번 피보나치를 잘 설정한다면 풀 수 있다.

그 이후에는 원래 피보나치를 구하는 것과 같이 arr[i] = arr[i-1] + arr[i-2]를 하면 된다.

이 식이 그대로 적용되는 이유는 N번째 수를 구하기 위해서는 N번과 N-1번째 수가 필요하고 그 과정을 쭉쭉..

하면 결국 0번과 1번을 호출하게 되는데 그 과정에서 저장된 값을 계속 사용해야 하기 때문이다.

 

 

4. 코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			int N = Integer.parseInt(br.readLine());
			if(N == 0) {
				sb.append("1 0").append("\n");
			}
			else if(N==1) {
				sb.append("0 1").append("\n");
			}
			else {
				int[] zero = new int[N+1];
				int[] one = new int[N+1];
				if(N>=2) {
					zero[1] = 0;
					one[1] = 1;
					zero[2] = 1;
					one[2] = 1;
					for(int i=3;i<N+1;i++) {
						zero[i] = zero[i-1]+zero[i-2];
						one[i] = one[i-1]+one[i-2];
					}
				}
				sb.append(zero[N]+" "+one[N]).append("\n");
			}
		}
		System.out.println(sb);
	}
}