[BAEKJOON]2748 피보나치 수 2

문제 요약

• 알고리즘 분류: dp
• 난이도:  Bronze1
• 문제내용:
  • 피보나치 수는 0과 1로 시작한다. 피보나치 식은 아래와 같다.
    • Fn = Fn-1 + Fn-2 
  • N이 주어 졌을때 피보나치 Fn을 구하여라 (N <= 90 자연수)

• 사이트: https://www.acmicpc.net/problem/2748

문제풀이

이번 문제는 재귀 호출로 풀기에는 숫자가 커질수록 계산량이 급격히 증가하기 때문에, 동적 계획법(Dynamic Programming, DP*을 사용해야 효율적으로 해결할 수 있다. 동적 계획법에 대해 잘 모르신다면, 아래 링크를 통해 자세한 설명을 확인 해보면 된다.
https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

이번 문제에는 간단한 동적계획법 문제라서  dp배열 또는 리스트 선언해서 dp[0] = 0, dp[1] = 1로 지정 하고 그 뒤에는 N까지 아래 점화식으로 구현 한다.

• dp[N] = dp[N - 1] + dp[N - 2]

위와 같이 동적 계획법을 사용하면, 배열을 한 번 순회하며 계산하기 때문에 시간 복잡도는 O(N) 나온다.

Code

Python

N = int(input())
# 피보나치 초기값 설정
dp = [0 for _ in range(N + 2)]
dp[1] = 1

# 2번째부터 N번째 피보나치 수 계산
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N])

.

Java

N=90일 때, 계산 결과는 2880067194370816120이 됩니다.이 값은 숫자가 매우 크기 때문에 int 타입으로 처리할 수 없다. 그 이유는 다음과 같다:

• int 타입은 4바이트 크기로, 표현할 수 있는 최대 값이 2,147,483,647 이다.
• 반면, long 타입은 8바이트 크기로, 최대 값이 9,223,372,036,854,775,807까지 표현 가능하다.

따라서 N이 큰 값을 가지는 문제에서는 long 타입을 사용해야 올바른 결과를 얻을 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		int N = Integer.parseInt(br.readLine());

		// 피보나치 초기값 설정
		long[] dp = new long[N + 2];
		dp[0] = 0;
		dp[1] = 1l;

		// 2번째부터 N번째 피보나치 수 계산
		for (int i = 2; i <= N; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}

		System.out.println(dp[N]);

	}
}