백준 [DP] Java 풀이 : 2748. 피보나치 수 2

2748. 피보나치 수 2

 

출처 : Baekjoon Online Judge

이 문제는 다이나믹 프로그래밍(DP, 동적계획법)으로 푸는 문제이다.

 

재귀로 풀었더니 시간초과로 틀렸다.

재귀로 푼 문제 풀이

 

package tag.dp;

import java.util.Scanner;

public class No2748 {
	
	/**
	 	[DP] Silver05 - 2748. 피보나치 수 2
	 */
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//입력받을 수
		int n = sc.nextInt();
		
		//피보나치 계산
		int result = fibonacci(n);
		
		System.out.print(result);
	}
	
	public static int fibonacci(int num) {
		if(num == 0) return 0;
		else if(num == 1) return 1;
		else return fibonacci(num-1) + fibonacci(num-2);
	}
}

 

그래서 배열로 풀어봤다.

 

배열로 푼 문제 풀이

package tag.dp;

import java.util.Scanner;

public class No2748 {

	/**
	 * [DP] Silver05 - 2748. 피보나치 수 2
	 */

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 입력받을 수
		int n = sc.nextInt();
		// 피보나치 결과 값을 저장할 배열
		long[] arr = new long[n + 1];

		// 피보나치 계산
		for (int i = 0; i <= n; i++) {
			if (i == 0)
				arr[i] = 0;
			else if (i == 1)
				arr[i] = 1;
			else
				arr[i] = arr[i - 1] + arr[i - 2];
		}

		System.out.print(arr[n]);
	}

}

 

n이 90일 때, 결과값이 int형을 벗어나서 배열을 long으로 선언해줘야 한다.