[BOJ 백준] 피보나치 수 2(2748) C++, Java

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

2748번: 피보나치 수 2

 

문제 설명 : 

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

 

출력 : 

첫째 줄에 n번째 피보나치 수를 출력한다.

 

예제 입력 : 

10

 

 

예제 출력 : 

55

 

 

 

접근법 : 

1) 어떻게 풀 것인가?

피보나치 수는 이 전 두 수의 합이다.

"이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다."

라는 문제 조건을 그대로 코드로 구현하기만 하면 된다.

n이 최대 90이므로 최대 90번만 연산하면 답을 구할 수 있는 문제이다.

 

이 문제는 문제 조건을 단순 구현하는 문제이지만 넓게보면 DP문제이기도 하다.

 

Dynamic Programming. 동적계획법이라는 거창한 이름을 가진

'DP'는 점화식을 통해 메모하여 연산을 줄인다.

는 간단한 원리에서 출발한다.

 

즉, 어떤 값이 들어오는지에 따라 결과값은 Dynamic하게 변화하지만

배열 등 자료구조에 값을 메모이제이션(Memoization, 이전 계산한 값을 기록해서 연산을 줄이는 기법)

해서 연산을 줄이는 것이다.

 

이 문제에서는 90번 연산을 하면 해당 값이 int 2^32 (약 21억)을 초과할 수 있다만 염두해두고,

그 배열을 long 으로 선언해주기만 하면 된다. 

(솔직히 긴가민가해서 로컬에서 long 배열로 돌려봤더니 범위 초과 - 90번째 피보나치수 : 2,880,067,194,370,816,120)

 

2) 시간복잡도

dp[i] = dp[i-1] + dp[i-2] 라는 점화식을 N번 실행하면 되므로 시간복잡도 O(N) = 90

C기준 0ms 가능하고 Java 기준 기본 입출력이 있지만 100ms 미만 예상

(Java 기준 -  80ms)

 

3) 공간복잡도

최대 90개의 피보나치 수가 나오므로 90*8Bytes(long) = 720Bytes 여유 넘친다.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

문제 자체는 쉽지만 DP에 대한 기본원리를 익힐 수 있다.

 

피보나치 관련 더 어려운 문제를 원할 경우 피보나치 수 3 추천.

N이 무려 1,000,000,000,000,000,000 = 백 경이다.

N의 시간복잡도로는 어림없고 logN 과 관련된 로직을 써야한다는 것을 짐작할 수 있다.

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

2749번: 피보나치 수 3

 

C++ 코드 : 

// 피보나치수2 2748 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

int n;
long long dp[91];

using namespace std;

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	// 2. N까지 피보나치 점화식을 수행한다
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	printf("%lld", dp[n]);

	return 0;
}

/*
int dfs(int n){
	if (n == 1 || n== 2) return 1;
	return dfs(n-1)+dfs(n-2);
}
*/

#endif

 

Java 코드 : 

// 피보나치수2 백준 2748
public class Main {
	
	static int N;				// N 피보나치 수
	static long[] dp;			 // 피보나치 수 dp 기록용 배열
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// N 입력
		N = Integer.parseInt(br.readLine());
		
		// N+1만큼 dp 배열 선언
		dp = new long[N+1];
		
		dp[0] = 0;
		dp[1] = 1;
		
		// 피보나치 점화식에 따라 N까지 dp 배열 채워줌
		for (int i=2;i<=N;i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		// N 번째 피보나치 수 출력
		bw.write(String.valueOf(dp[N]));
			
		bw.flush();
		bw.close();
		br.close();
	}
}