1003번: 피보나치 함수(백준 C++)

1003번: 피보나치 함수 링크

코드

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

vector <pair<long long, long long>> fb;

void fibo(int n){
    if(fb.size() <= n){
        for(int i=fb.size(); i<=n; i++){
            fb.push_back(make_pair((fb[i-2].first + fb[i-1].first), (fb[i-2].second + fb[i-1].second)));
        }
    }
    printf("%lld %lld\n", fb[n].first, fb[n].second);
}
int main() {
    fb.push_back(make_pair(1, 0)); // n == 0
    fb.push_back(make_pair(0, 1)); // n == 1
    int t, n;
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        scanf("%d", &n);
        fibo(n);
    }
}

풀이 및 사견

어제 피보나치 문제를 풀면서 사골이라고 한 것에는 이유가 있다.
오늘도 사골나치문제이기 때문이다. 사실 피보나치 원리는 같은건데 그거 하나로 이렇게 다양하게 우려먹을 수 있다는게
되려 피보나치의 대단함을 증명하는 것이 아닐까?

오늘도 수학귀신 피보나치로 연전연승이다.

어쨌든 그래도 아예 생판 모르는 문제를 푸는것보다는 아는거에 대해 푸는게 낫다고 생각한다.
한 번 풀어보자.

문제

• 최소 문제를 한 번 이상 읽고 온 방문자를 가정하에 작성된 글입니다.

피보나치 수를 재귀로 구현한다고 생각해보자.
N = 0 인 경우에는 0을 1번 반환한다. 1을 0번 반환한다.
N = 1 인 경우에는 0을 0번 반환한다. 1을 1번 반환한다.
N = 2 인 경우에는 0을 1번 반환한다. 1을 1번 반환한다.
N = 3 인 경우에는 0을 1번 반환한다. 1을 2번 반환한다.

눈치 채셨습니까? 결국 N이 몇이든 그때의 피보나치 수는
0 * (0이 반환된 횟수) + 1 * (1이 반환된 횟수) 이며,
이 반환된 횟수는 피보나치 수열 점화식과 동일하게

• 0n -> 0이 주어진 수 N에서 반환된 횟수
• 1n -> 1이 주어진 수 N에서 반환된 횟수

0n = 0n-1 + 0n-2
1n = 1n-1 + 1n-2

이와 같습니다. 그렇게 되면 문제 풀이는, 어려울 게 없습니다. 이전에 하던 그대로 피보나치를 하면 됩니다.

벡터 선언

vector <pair<long long, long long>> fb;

저는 long long 타입을 pair로 갖는 Vector 변수를 선언했습니다.
이 변수의 first에는 0이 반환된 횟수, second에는 1이 반환된 횟수가 들어갑니다.
당연하게도, index는 주어진 수 N과 동일합니다.

즉, fb[3]은 (1, 2) 입니다.

함수

위에서 벡터를 만들었으면 풀이는 이제 반복문을 통해 벡터에 계속해서 피보나치를 업데이트 해 주면 됩니다.
아, 참고로 벡터 생성후 n이 0일때와 1일때는 임의로 추가를 해 주었습니다. 그렇지 않으면 문제 풀이가 안되니까요.

void fibo(int n){
    if(fb.size() <= n){
        for(int i=fb.size(); i<=n; i++){
            fb.push_back(make_pair((fb[i-2].first + fb[i-1].first), (fb[i-2].second + fb[i-1].second)));
        }
    }
    printf("%lld %lld\n", fb[n].first, fb[n].second);
}

이 문제는 n을 한 번만 받고 끝나는 문제가 아니죠.
테스트 케이스의 개수 T만큼 받습니다.

그런데 n을 T만큼 받는다고해서, 받을때마다 피보나치 수를 0부터 계산하는건, 글쎄요 조금 비효율적이지 않나 싶었습니다.

그래서 주어진 n이 vector fb의 크기보다 크면 아직 n까지 피보나치를 구하지 못했다는 뜻이므로
이전에 구했던 구간 - (fb의 사이즈 크기) 부터 시작해서 n까지 구합니다.

반대로 n이 vector fb의 크기보다 작으면 이미 구했다는 뜻이므로
바로 vector를 참조해서 출력해주면 조금은 더 빠르게 답을 구할수 있을겁니다.