득이공간

[백준 C++] 1003 피보나치 함수 - 다이나믹프로그래밍 본문

PS/알고리즘 문제풀이

[백준 C++] 1003 피보나치 함수 - 다이나믹프로그래밍

쟁득 2024. 2. 4. 16:53
 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

#include <iostream>
using namespace std;

pair<int, int> DP[41];

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

	DP[0] = make_pair<int, int>(1, 0);
	DP[1] = make_pair<int, int>(0, 1);
	for (int i = 2; i < 41; ++i)
	{
		DP[i].first = DP[i - 1].first + DP[i - 2].first;
		DP[i].second = DP[i - 1].second + DP[i - 2].second;
	}

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

다이나믹 프로그래밍 문제입니다.

0과 1이 각각 몇번 호출되는지 정보를 담기위해 pair를 사용했고

바텀-업 방식으로 피보나치  점화식 이용해서  DP 테이블에 저장해주었습니다.