동적계획법1-1003-피보나치함수

문제

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

첫 번째 입력 : 테스트 케이스 개수 t
나머지 입력 t번 : n은 음이 아닌 정수

출력 : '0출력 횟수' '1출력 횟수'

접근 방법

동적 계획법의 조건 두 가지 모두 만족한다.

1. 작은 문제 반복
   2, 값이 바뀌지 않음

주어진 n은 계속 해서 쪼개질 것이다.
fibonacc(3) -> 1 2
fibonacc(2) -> 1 1
fibonacc(1) -> 0 1
fibonacc(0) -> 1 0

fibonacc(4) -> fibonacc(3)의 출력 + fibonacc(2)의 출력 결과
fibonacc(5) -> fibonacc(4)의 출력 + fibonacc(3)의 출력 결과

나의 답안

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

void count(int n, vector<pair<int, int>>& memory)
{
    memory.push_back(make_pair(1, 0));
    memory.push_back(make_pair(0, 1));

    for (int i = 2; i <= n; i++) 
        memory.push_back(make_pair(memory[i - 1].first + memory[i - 2].first, memory[i - 1].second + memory[i - 2].second));
}

int main()
{
    int t;
    cin >> t;
    vector<int> n(t);
    vector<pair<int, int>> memory; //<0출력수, 1출력수>

    for (int i = 0; i < t; i++) 
        cin >> n[i];

    int max = *max_element(n.begin(), n.end()); //n의 최댓값 구하기

    count(max, memory); //최댓값만 돌리기

    for (int i = 0; i < t; i++) 
        cout << memory[n[i]].first << " " << memory[n[i]].second << " " << endl;

    return 0;
}

시도 1 = 시간초과

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

void count(int n, pair<int, int>& cnt)
{
    if (n == 0)
        cnt.first++;
    else if (n == 1)
        cnt.second++;
    else {
        count(n - 1, cnt);
        count(n - 2, cnt);
    }
}

int main()
{
    int t;
    cin >> t;
    vector<int> n(t);

    for (int i = 0; i < t; i++)
        cin >> n[i];

    for (int i = 0; i < t; i++){
        pair <int, int> cnt = make_pair(0, 0);
        count(n[i], cnt);
        cout << cnt.first << " " << cnt.second << " " << endl;
    }
    return 0;
}

시도 1에 따른 해결방안 모색

시간초과!!!! 하위 문제를 해결한 후 저장한 뒤에 불러서 쓰는거랬다.
그렇다면 1, 0이외에도 앞에서 구한 값을 이용할 수 있다.