BOJ1003 - 피보나치 함수

풀이 없이 바로 솔브하여 사고 방식이 처음 PS를 본격적으로 시작한 1월 8일보다 그래도 성장했음을 느꼈던 문제이다. 

 

문제번호

BOJ1003 - 피보나치 함수

 

문제설계

단순 피보나치 구현이 아니라

재귀의 중복 호출 -> 시간초과 -> DP 전환을 유도하는 문제

DP : dynamic programming

 

생각한 문제 패턴

피보나치 수 n이 40 이하로 작음 

재귀 함수 처리시, subroutine 많이 생성되므로 그만큼 동작 시간에 TLE 가능성 염두

점화식 존재 + 중복 계산 발생 → 1차원 DP 패턴

 

내가 생각한 알고리즘

 0과 1 호출 횟수를 각각 저장하는 DP 테이블 생성. → pair로 생성

(추천은 struct 방식도 있었음)

fibo[i] = fibo[i-1] + fibo[i-2] 점으로 0~40까지 미리 계산 후, 각 테스트케이스는 O(1) 출력.

 

잘못됨 판단 신호

재귀 + 피보나치 = 지수 시간복잡도.

같은 값이 여러 번 계산되는 구조

 

첫 접근했을때 생각

재귀 함수로 돌려서 그때마다 cnt 값 더하는 방식으로 생각했었는데

그대로 쓰면 호출 수가 2ⁿ으로 폭증 → TLE 확정.

처음부터 재귀 금지, DP라고 판단.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;

	vector<pair<int, int>> fibo(41);

	fibo[0] = {1,0};
	fibo[1] = {0,1};

	for(int i =2; i<=40; i++)
	{
		fibo[i].first = fibo[i-1].first + fibo[i-2].first;
		fibo[i].second = fibo[i-1].second + fibo[i-2].second;
	}

	cin>>T;
	for(int i = 0; i<T; i++)
	{
		int number;
		cin>>number;
		cout<<fibo[number].first<<" "<<fibo[number].second<<'\n';
	}
}