[2747] 피보나치 수

출처 : www.acmicpc.net/problem/2747

2747번: 피보나치 수

풀이과정

1. 재귀함수를 이용하여 구현한다.

 

---

작성코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		bw.write(String.valueOf(func(n)));
		br.close();
		bw.flush();
		bw.close();
	} // main

	private static int func(int cal) throws IOException {
		if (cal == 0)
			return 0;
		else if (cal == 1)
			return 1;
		else
			return func(cal - 1) + func(cal - 2);
	} // func

} // MainNew

 

참고코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int a = 0;
		int b = 1;
		while (n > 0) {
			int temp = a;
			a = b;
			b = temp + b;
			n--;
		}
		
		System.out.println(a);
	}

}

 

memo

bufferdwriter 사용시 int는 string 변환 출력해야 된다는 것을 알았다.

작성코드는 값은 나오지만 시간 초과로 통과하지 못했다.

재귀 구현 연습용 문제였다.

 

+

피보나치 수, 점화식 같은 문제는 재귀로 구현은 가능하지만 연산 시간이 굉장히 많이 걸린다.

예를 들면, func(4) 를 호출 하였을때 func(1) 함수는 그 과정에서 다섯번 호출된다.

호출되는 함수를 트리 형태로 그려보면 알 수 있다.

그래서 내가 작성한 재귀 함수의 연산속도는 2의 n제곱이 되면서

문제에서 말한 최대 n이 45가 된다면

2의 45제곱은 연산하기에는 너무 큰 수라서 시간초과 발생할 수 밖에 없던 코드 였음, 재귀가 아닌 단순 반복문으로 푸는게 맞음