[BOJ 2748번] 피보나치 수 2(JAVA)

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

2748번: 피보나치 수 2

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int n=Integer.parseInt(br.readLine());
		long a=0, b=1, c=0;
		if(n==1) {
			System.out.println(1);
			return;
		}
		else if(n>=2){
			for(int i=1; i<n; i++) {
	   			c=a+b;
	   			a=b;
	   			b=c;
	   		}
	   	System.out.println(c);
		}
	}
}

 원래 피보나치 함수의 정의인 f(n)=f(n-1)+f(n-2)를 이용해서 재귀를 이용해서 문제를 풀어보면 코드가 아래와 같이 나옵니다.

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int n=Integer.parseInt(br.readLine());
		System.out.println(fibo(n));
	}
	
	static int fibo(int num) {
		if(num==0) return 0;
		else if(num==1) return 1;
		else {
			return fibo(num-1)+fibo(num-2);
		}
	}
}

 하지만 이 문제에서는 시간 초과가 일어납니다.

따라서 위의 코드와 같이 작성을 해야 합니다.

변수 a, b, c를 선언하고 초기 값을 a=0, b=1로 설정한 후, for 문에서 c=a+b; a=b; b=a; 를 반복해서 돌려줍니다.

이렇게 되면 a값과 b값은 각각 c값의 전과 전전 값으로 할당이 되므로 피보나치의 정의가 유지됩니다.

 

그리고 이 문제를 푸실 때 주의하셔야하는 점은, a, b, c값을 int로 나타낸다면, 숫자가 커졌을 때에 오버플로우가 발생하게 되므로 자료형을 long으로 설정해주시는 게 좋습니다.