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

백준 온라인 저지(BOJ) 24416번 알고리즘 수업 - 피보나치 수 1

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

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

* 사용언어 : C언어, C++

 

1. 문제

n의 피보나치 수를 2가지 방식으로 구할 때 두 코드의 실행 횟수를 출력

(① 재귀, ② 동적 계획법)

 

2. 풀이

동일한 연산의 반복으로 결과값을 구하는 경우 top-down 방식, bottom-up 방식으로 구분이 되는데

두 가지 방식을 구현해보고 비교해볼 수 있는 문제입니다.

 

문제 풀이 자체는 단순하니 주어진 의사 코드를 본인이 사용하는 언어에 맞추어 구현만 하면 됩니다.

 

한 가지 주의할 점은 의사 코드 상에 # 코드 1, # 코드 2라고 표시된 부분에서

count를 증가시켜주어야 정확한 정답이 됩니다.

 

저는 문제를 대충 읽고 # 코드 1을 제 마음대로 fib호출 처음에 넣었다가 답이 틀려서 한참 헤맸었습니다.

SW 개발은 고객(문제)의 요구사항을 정확히 파악하는 것이 가장 중요한 것 같습니다.

 

추가로 # 코드 2는 for문 내에서 굳이 1씩 증가시킬 필요가 없어보여서

for문 종료 후 반복 횟수를 한 번에 계산하였습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24416_알고리즘 수업 - 피보나치 수 1
1116KB	224ms
*/
#include <cstdio>

const int LM = 41;
int f[LM], N, c1, c2;

int fib(int n) {
	if (n == 1 || n == 2) {
		++c1;
		return 1; // code 1
	}
	return fib(n - 1) + fib(n - 2);
}

int fibonacci(int n) {
	f[1] = f[2] = 1;
	for (int i = 3; i <= n; ++i) {
		f[i] = f[i - 1] + f[i - 2]; // code 2
	}
	c2 = n - 2;
	return f[n];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	fib(N);
	fibonacci(N);
	printf("%d %d\n", c1, c2);
	return 0;
}