[BJ1003] 피보나치 함수

 백준 - 피보나치 함수 

문제 링크

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

1003번: 피보나치 함수

 

문제 입출력

3
0
1
3

1 0
0 1
1 2

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;


public class Main {
	static int ans0, ans1, T, N;
	static int[] zeros, ones;


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			// 초기화
			N = Integer.parseInt(br.readLine());
			zeros = new int[N + 2]; // i 일떄의 0의 갯수
			ones = new int[N + 2]; // i 일때의 1의 갯수

			// 풀이
			sol();

			// 출력
			System.out.println(zeros[N] + " " + ones[N]);
		}

	} // end main


	private static void sol() {
		// 기저 memoi 값 초기화
		zeros[0] = 1;
		zeros[1] = 0;
		ones[0] = 0;
		ones[1] = 1;

		// bottom-up 방식 (반복문)
		for (int i = 2; i <= N; i++) {
			zeros[i] = zeros[i - 2] + zeros[i - 1];
			ones[i] = ones[i - 2] + ones[i - 1];
		}

	} // end sol

	// 이렇게 하면 시간 초과
	// private static int fibo(int n) {
	// if (n == 0) {
	// ans0++;
	// return 0;
	// } else if (n == 1) {
	// ans1++;
	// return 1;
	// } else return fibo(n - 1) + fibo(n - 2);
	//
	// } // end fibo
}

재귀를 이용하여 피보나치 문제를 풀었을 때, 기저에 다다르는 0과 1의 갯수는 몇개인가를 구하는 문제.

시간 제한이 0.25s 라서 재귀를 이용해서 풀면 시간 초과가 난다.

재귀를 이용해서 푼다면 O(2^N) 이 되고 => 2^40 이 되는데
대략적으로 2^10 == 10^3 이므로
2^40 은 == 10^12 가 되어 가당치도 않게 된다.

따라서 다이나믹 프로그래밍을 이용하여 문제를 풀어야 한다.

bottom-up 방식을 이용하여 작은 문제부터 쌓았다. memoi 배열을 2개 선언해준다. (zeros, ones)

피보나치와 마찬가지로 해당 배열이 쌓이는 점화식도 d[i] = d[i-2] + d[i-1] 이므로 똑같이 쌓으면 된다.

 

 

 

 

 

 

 

 

#백준 피보나치함수 자바 #백준 피보나치함수 java #백준 피보나치함수 시간복잡도

---