백준 1003 c++ "피보나치 함수" -PlusUltraCode-

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

 

[필자 사고]

동적 프로그래밍 bottom-up 방식으로 푼 문제이다.

필자는 pair<int,int> 을 이용하여 첫번째 인덱스에는 0의 갯수를

두번째 인덱스에는 1의 개숫를 bottom-up 방식으로 늘려갔다.

점화식은 아래 코드해설 부분에 설명해 놓았다.

[코드 해설]

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<pair<int, int>> dp;

void Make_DP() {
	dp.resize(41);

	dp[0] = { 1,0 };
	dp[1] = { 0,1 };
	dp[2] = { 1,1 };

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

}

void Game_Start() {
	int N;
	cin >> N;

	cout << dp[N].first << " " << dp[N].second << '\n';
}

int main(void) {
	int T;
	cin >> T;
	Make_DP();
	while (T--) {
		Game_Start();
	}
}