[백준] 24416번: 알고리즘 수업 - 피보나치 수 1 [C++]

 

알고리즘 분류: 수학, 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

 

 

【 풀이 】

 

수학적 사고와 동적계획법을 이용하여 해결하는 문제이다.

문제에서 원하는 건 피보나치 수를 저장하는 배열 F가 주어졌을 때,

F[n]에 해당하는 피보나치 수를 구하는 데 필요한 코드1에 해당하는 한 줄, 코드2에 해당하는 한 줄이

각각 몇번 실행되는지를  구하는 것이다.

직접 해보면 알 수 있지만, 결국 코드1은 n이 1이 되었을 때 실행되는 줄이기 때문에 F[n] 만큼 실행될 것이다.

코드2는 동적계획법으로, F[n]까지 구하는 데 F[1] 값과 F[2] 값만 있으면

n까지의 피보나치 수를 구할 수 있기 때문에n-2만큼 실행될 것이다.

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int main(void) {
	int f[100] = { 0 };
	f[0] = 0, f[1] = 1, f[2] = 1;
	int n;
	cin >> n;
	for (int i = 3; i <= n; i++) {
		f[i] = f[i - 2] + f[i - 1];
	}
	cout << f[n] << ' ' << n-2;
	return 0;
}