[Baekjoon] 1003번: 피보나치 합

🥅 문제

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

 

🔍 설계

재귀 함수로 설계할 경우, 시간 초과가 발생할 것이다.

 

fibonacci(N)을 출력했을 때, 0과 1의 호출 횟수는 fibonacci(N-1)과 fibonacci(N-2)의 0과 1의 호출 횟수와 관련이 있으므로, 다이나믹 프로그래밍을 이용하여 해결할 수 있다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int t, n;
vector<pair<int, int>> dp(41, {0, 0});

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> t;
	dp[0].first = 1;
	dp[1].second = 1;
	for (int i=2; i<=40; i++){
		dp[i].first = dp[i-1].first + dp[i-2].first;
		dp[i].second = dp[i-1].second + dp[i-2].second;
	}
	for (int j=0; j<t; j++){
		cin >> n;
		cout << dp[n].first << " " << dp[n].second << "\n";
	}
	return 0;
}

 

📝 메모

A의 값을 구하는데 B와 C의 값을 이용한다면, 다이나믹 프로그래밍을 이용할 수 있다.