백준 24416 알고리즘 수업 - 피보나치 수 1

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

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

 

 

 

EXPLANATION

코드의 실행 횟수에서 코드는 fn = fn-1 + fn - 2를 말한다.

 

두 번째 코드는 N이 1, 2라면 f[i] = f[i - 1] + f[i + 1]가 실행되지 않을거고 

그 이외의 수라면 반복문 횟수(N - 2)만큼 실행될 것이다.

N은 5이상이므로 언제나 N - 2를 출력하도록 해도 된다. 

ex) 

N = 5일 때

f[3] = f[2] + f[1]

f[4] = f[3] + f[2]

f[5] = f[4] + f[3]

3회 실행

 

 

첫번째 코드는 

fib(n) {
    if (n = 1 or n = 2)
    then return 1;
    else return (fib(n - 1) + fib(n - 2));	//return int fib = fib(n - 1) + fib(n - 2)랑 같다.
}

예를 들면서 설명하겠다.

갈라지는 곳에서  fib = fib(n - 1) + fib(n - 2) 코드 실행됨

리프 노드들을 모두 다 더하면  fn  이다.

그림에서 볼 수 있듯이 코드 실행 횟수는 리프 노드 1이 +되는 횟수와 같다.

따라서 실행횟수는 fn - 1이 되야 하는데

어째서인지 첫번째 예제를 보면 N = 5일 때 실행횟수는 fn인 5를 하고 있다.

두번째 예제도 N=30일 때 실행횟수는 fn인 832040.

그래서 그냥 fn이 첫번째 실행횟수의 코드가 되도록 작성했더니 맞았습니다. 라는 메세지를 얻었다.

이거 왜 그런 지 아시는 분 댓글로 알려주시면 정말 감사하겠습니다.

 

 

 

CODE

#include <iostream>
using namespace std;
typedef long long ll;

ll fib[41];    //for i[1, 40]

int main() {

	fib[1] = fib[2] = 1;
	for (int i = 3; i <=40; i++) fib[i] = fib[i - 1] + fib[i - 2];	//첫 번째 코드 실행 횟수 구하기(fib[N]

	int N; cin >> N;
	cout << fib[N] << ' ' << N - 2;	//두번째 코드 실행 횟수는 N - 2
}