[백준] 1003 / 피보나치 함수

// preset 생략

typedef pair<int, pair<int, int>> pipii;

map<int, pipii> memo;

pipii fibonacci(int n)
{
    if (n == 0)
    {
        return {0, {1, 0}};
    }
    else if (n == 1)
    {
        return {1, {0, 1}};
    }
    else
    {
        pipii f, s;
        if (memo.find(n - 1) != memo.end())
            f = memo[n - 1];
        else
            f = fibonacci(n - 1);

        if (memo.find(n - 2) != memo.end())
            s = memo[n - 2];
        else
            s = fibonacci(n - 2);
        f.first += s.first;
        f.second.first += s.second.first;
        f.second.second += s.second.second;
        memo[n] = f;
        return f;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    while (n--)
    {
        int y;
        cin >> y;

        pipii fi = fibonacci(y);
        cout << fi.second.first << " " << fi.second.second << "\n";
    }
}

피보나치 함수에서 결과값과 함께 0, 1을 사용한 횟수까지 return 하면 된다. 0.25초 시간 제한이 있으니 피보나치 함수의 결과값을 map을 통해서 저장했다.