1003번 피보나치 함수

문제링크 : www.acmicpc.net/problem/1003

1003번: 피보나치 함수

방법1. 재귀함수 (시간복잡도 : O(2^N))  => 시간 초과

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
	
	static int zero =0;
	static int one = 0;
	
	public static int fibonacci(int i) {
		if (i==0) {
			zero+=1;
			return 0;
		}
		else if(i==1) {
			one+=1;
			return 1;
		}
		else return fibonacci(i-1)+fibonacci(i-2);
	}
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder();
		try {
			int N = Integer.parseInt(bf.readLine());
			for (int n = 0;n<N;n++) {
				try {
					zero=0;
					one=0;
					
					int a = Integer.parseInt(bf.readLine());
					int answer = fibonacci(a);
					sb.append(zero+" "+one+"\n");
				} catch(IOException e) {}
			}
			System.out.println(sb);
		} catch(IOException e) {}
	}
}

방법2. 동적프로그래밍 (시간복잡도 : O(N^2)) => 시간 : 172ms

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

public class Main{
	static int arr[] = new int[41];
	public static int fibonacci(int n) {
		if(n==0) {
			arr[n] = 0;
			return 0;
		}
		else if(n==1) {
			arr[n] = 1;
			return 1;
		}
		if(arr[n]!=0) {return arr[n];}
		else {
			return arr[n] = fibonacci(n-1)+fibonacci(n-2);
		}
	}
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		try {
			int N = Integer.parseInt(bf.readLine());
			for(int i=0;i<N;i++) {
				try {
					int A = Integer.parseInt(bf.readLine());
					if(A==0) {
						sb.append("1"+" "+"0"+"\n");
					}
					else if(A==1) {
						sb.append("0"+" "+"1"+"\n");
					}
					else{
						fibonacci(A);
						sb.append(arr[A-1]+" "+arr[A]+"\n");
					}
					
				}catch(IOException e) {}
			}
			System.out.println(sb);
		}catch(IOException e) {}
	}
}

방법3. 반복문 (시간복잡도 : O(N)) =>시간 : 164ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder();
		try {
			int N = Integer.parseInt(bf.readLine());
			for(int i =0;i<N;i++) {
				try {
					int target = Integer.parseInt(bf.readLine());
					
					int list[][] = new int[41][2];
					list[0][0] = 1;
					list[0][1] = 0;
					list[1][0] = 0;
					list[1][1] = 1;
					
					for(int j = 2;j<=target;j++) {
						list[j][0] = list[j-1][0]+list[j-2][0];
						list[j][1] = list[j-1][1]+list[j-2][1];
					}
					
					sb.append(list[target][0]+" "+ list[target][1]+"\n");
				}
				catch(IOException e) {}
			}
			System.out.println(sb);
		}
		catch(IOException e) {}
	}
}

 

 

참고1 : galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

참고2 : makefortune2.tistory.com/60

28. 피보나치 수열( 재귀, 동적 프로그래밍, 반복) 모든 방식 알고리즘