[C++] 1003번 피보나치 함수

문제

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

---

풀이

2025.01.13 - [분류 전체보기] - [C++] 다이나믹 프로그래밍

[C++] 다이나믹 프로그래밍

1. 문제 분석

F(0)이 호출될 때마다 0이 출력되고, F(1)이 호출될 때마다 1이 출력

문제는 F(n)을 계산할 때 총 몇 번 0과 1이 호출되는지를 구하는 것

재귀의 비효율성

단순히 재귀로 계산하면, 같은 값에 대해 중복 호출이 많이 발생하여 비효율적

• F(5) 계산 시:
  • F(5)는 F(4)와 F(3)을 호출
  • F(4)는 F(3)과 F(2)를 호출
  • 이런 식으로 F(3) 같은 값이 반복적으로 호출, 이를 효율적으로 해결하기 위해 DP(메모이제이션) 사용

---

2. 다이나믹 프로그래밍 점화식 도출

피보나치 수열의 특성상, F(n)의 호출 횟수는 F(n-1)과 F(n-2)의 호출 횟수의 합

• dp[i].first: F(i) 계산 시 0이 호출된 횟수
• dp[i].second: F(i) 계산 시 1이 호출된 횟수

점화식

dp[i].first=dp[i−1].first+dp[i−2].firstdp[i].first = dp[i-1].first + dp[i-2].first dp[i].second=dp[i−1].second+dp[i−2].seconddp[i].second = dp[i-1].second + dp[i-2].second

• dp[i-1]은 F(i-1)을 계산할 때 호출된 횟수
• dp[i-2]은 F(i-2)을 계산할 때 호출된 횟수
• 따라서, F(i)에서 0과 1이 호출된 횟수는 각각 F(i-1)과 F(i-2)의 호출 횟수를 더한 값

 

---

코드

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

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

    int t;
    cin >> t;

    vector<pair<int, int>> dp(41); 
    dp[0] = { 1, 0 }; // 0을 호출한 횟수, 1을 호출한 횟수
    dp[1] = { 0, 1 };

    for (int i = 2; i <= 40; i++) {
        dp[i].first = dp[i - 1].first + dp[i - 2].first; // 0의 호출 횟수
        dp[i].second = dp[i - 1].second + dp[i - 2].second; // 1의 호출 횟수
    }

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << dp[n].first << " " << dp[n].second << endl;
    }

    return 0;
}