[백준 2748번] [C언어] 피보나치 수 2

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

2748번: 피보나치 수 2

 

난이도 : 브론즈 1
태그 : 수학, 다이나믹 프로그래밍

 

 

설명

피보나치 수는 재귀를 배울 때, 예시로 많이 쓰이지만, 다이나믹 프로그래밍(동적 계획법)의 예제로도 많이 쓰이죠.

이 문제 같은 경우는 재귀로는 풀 수 없으며, 다이나믹 프로그래밍(이하 dp)을 사용해 풀 수 있습니다.

 

DP는 동적 계획법으로 번역할 수 있는데,

간단히 말하자면, 이전의 구한 값을 저장해놨다가, 다음 값을 구하기 위해 사용하는 것을 말합니다.

분할 정복 알고리즘과도 비슷하며, 최적화 기법 중 하나입니다.

 

DP의 대한 설명을 봤을때, 뭐가 다이나믹하지? 라고 생각이 들 수도 있는데,

이에 대해 찾아보니, DP의 고안자인 벨만 포드가

그냥 다이나믹이라는 단어가 멋있어서 별 의미 없이 붙였다고 합니다 (...)

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {

	long long dp[91] = {0};
	int n;
	scanf("%d", &n);
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	printf("%lld", dp[n]);

	return 0;
}

 

피보나치 수열의 경우, 앞의 두 값의 합이 다음 값의 합이 되므로,

dp의 첫번째, 두번째 값을 초기화하고,

이후의 값은 dp[i] = dp[i-1] + dp[i-2] 로 일반화할 수 있습니다.

이처럼 dp는 점화식과 같은 문제를 그대로 코드로 옮길 수 있습니다.

 

 

후기

DP의 기본격인 문제로써,

알고리즘 시간 때, 이 문제를 처음 접했는데,

이때까지만 하더라도 dp가 먼 미래에 큰 빠따를 들고 기다리고 있을 줄은 몰랐습니다.