10870 피보나치 수 5 자바

맨 처음엔 문제만 읽고 for문으로 풀었는데...

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int f2 = 0;// f(n-2)
		int f1 = 1;// f(n-1)
		int f = 0; // f(n)

		if (n == 0) {// 0번째 피보나치 수는 0
			f = 0;
		} else if (n == 1) {// 1번째 피보나치 수는 0
			f = 1;
		} else {
			for (int i = 1; i < n; i++) {
				f = f1 + f2;// n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한값
				f2 = f1;// 다음 f(n-2)번째 피보나치 수를 f(n-1)번째 숫자로 치환
				f1 = f;// 다음 f(n-1)번째 피보나치 수를 f(n)번째 숫자로 치환
			}
		}

		System.out.println(f);
    }
}

 

다시 보니.. 문제의 단계가 '재귀'였다.

그래서 재귀함수를 이용해서 다시 풀어보았다.

import java.util.*;
public class Main{
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(pivo(n));
	}

	public static int pivo(int n) {
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;

		return pivo(n - 1) + pivo(n - 2);
	}
}

 

검색해보니 저런식으로 하면 n의 크기가 클수록 pivo 함수도 계속 반복되기 때문에

효율적이지 않다고 한다..!