득이공간
[백준 C++] 1003 피보나치 함수 - 다이나믹프로그래밍 본문
#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 테이블에 저장해주었습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 11726 2xn 타일링 - 다이나믹프로그래밍 (0) | 2024.02.04 |
---|---|
[백준 C++] 9095 1, 2, 3 더하기 - 다이나믹프로그래밍 (0) | 2024.02.04 |
[백준 C++] 11659 구간 합 구하기 4 - 자료구조 (0) | 2024.02.03 |
[백준 C++] 1966 프린터 큐 - 자료구조 (0) | 2024.02.03 |
[백준 C++] 1253 좋다 - 자료구조 (1) | 2024.02.03 |