#2747 : 피보나치 수

풀이방법

2022.01.22

재귀함수로 구현하면 제한시간 1초 내에 해결할 수 없는 문제이다.

반복문을 사용해 정수 배열에 피보나치 수들을 미리 저장해놓고 꺼내쓰면 빠르게 해결할 수 있다.

n<= 45이므로 45번째 피보나치 수까지만 구해놓으면 된다.

 

코드

Java(2022.01.22)

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int[] fib = new int[45];
		fib[0] = 1;
		fib[1] = 1;
		
		for(int i = 2; i<45; i++) {
			fib[i] = fib[i-1] + fib[i-2];
		}
		
		System.out.print(fib[n-1]);		
	}
}

재귀함수로 구현할 경우

import java.io.*;

public class Main {

	public static int fib(int n) {
		if(n <= 2) return 1;
		else return fib(n-1) + fib(n-2);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		System.out.print(fib(n));		
	}
}