백준 1003 - 피보나치 함수

피보나치 함수에 정수 n을 넣었을 때 1과 0이 몇번 나오는지 출력하는 문제입니다.

처음에는 단순하게 피보나치 함수를 실제로 계산해 0과 1의 개수를 구했지만 Time complexity가 $O(N^2)$이기에 시간 초과가 발생했습니다.

피보나치 함수에서 0과 1의 개수를 보면 패턴이 있음을 알 수 있습니다.

fib	0	1
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21
9	21	34

6을 예시로 들면 fib(6)에서 0의 개수는 fib(5)의 0의 개수와 fib(4)의 0의 개수를 더한 것과 같습니다.
이를 활용해 fib(0)과 fib(1)의 0과 1의 개수를 미리 넣어두고 2부터 문제에서 최대 수인 40까지 0과 1의 개수를 구해놓을 수 있습니다.

#include <iostream>
#include <vector>

int main()
{
    std::vector<std::pair<int, int>> cntvec;

    cntvec.push_back({ 1, 0 });
    cntvec.push_back({ 0, 1 });

    int cnt;
    std::cin >> cnt;

    for (int i = 2; i <= 40; i++)
    {
        cntvec.push_back({ cntvec[i - 1].first + cntvec[i - 2].first, 
            cntvec[i - 1].second + cntvec[i - 2].second });
    }

    for (int i = 0; i < cnt; i++)
    {
        int temp;
        std::cin >> temp;

        std::cout << cntvec[temp].first << " " << cntvec[temp].second << "\n";
    }

	return 0;
}

이렇게 Time complexity를 $O(N)$으로 줄일 수 있습니다.

위 테이블에서 또다른 특징을 찾아 더 효율적인 방식으로 해결할 수 있습니다.
표를 보면 fib(n)의 0의 개수는 fib(n - 1)의 1의 개수와 동일함을 확인할 수 있습니다.

이를 이용해 메모리 사용량을 반절 줄일 수 있습니다.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> onecnt = { 0, 1 };

    int cnt;
    std::cin >> cnt;

    for (int i = 2; i <= 40; i++)
        onecnt.push_back(onecnt[i - 1] + onecnt[i - 2]);

    for (int i = 0; i < cnt; i++)
    {
        int temp;
        std::cin >> temp;

        if (temp == 0)
            std::cout << "1 0\n";
        else
            std::cout << onecnt[temp - 1] << " " << onecnt[temp] << "\n";
    }

	return 0;
}

---

해당 글을 참고해 문제를 해결하는데 도움을 받았습니다.