[백준,BOJ 2748] 피보나치 수 2(JAVA 구현,추가풀이)

\

-내 생각

  우선 피보나치수열의 개념의 이해는 쉽다. 처음에는 동적 프로그래밍 알고리즘을 사용하는 과정에서 각 결괏값을 저장하는 배열을 int형으로 선언했는데, 수 들이 기하급수적으로 커지기 때문에 long타입으로 다시 선언해 주었다.

 

-해법

  코드는 간결하다.

 

import java.util.*;

public class Main {
	static int n;
	static long check[] = new long[91]; // long형 배열
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n= sc.nextInt();
		check[0]= 0; // 0번, 1번 숫자는 미리 저장해둔다.
		check[1] =1;
		
		for(int i=2;i<=n;i++) { // 2번 숫자부터 반복 시작
			check[i] = check[i-1] + check[i-2];
		}
		System.out.println(check[n]); // n번 째 숫자 출력
		
		
	}
	
}

---

  위 방식은 반복문을 활용한 bottom-up 방식이며 이번에는 재귀를 이용한 top-down 방식을 사용해보았다.

import java.util.Arrays;
import java.util.Scanner;

class Main {
	static int n;
	static long[] dp;
		
	static long fibonacci(int num) {
		if(num == 0) return dp[0];
		if(num == 1) return dp[1];
		
        // 초기값일 경우 재귀호출
		if(dp[num]==-1) {
			dp[num] = fibonacci(num-1) + fibonacci(num-2);		
		}
        // 아니면 그냥 메모이제이션된 값을 사용
		return dp[num];		
	}
	
	public static void main(String[] args)   {
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		dp = new long[n+1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		dp[1] = 1;
		
		System.out.println(fibonacci(n));
	}
}