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

문제

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



풀이

역시 동적 프로그래밍을 적용하여 순서대로 풀어나가면 된다. 문제는 어떤 N에 대하여 fibonacci(N)이 0과 1을 몇 번 호출하는지 구하는 것이다.

• pair에 0과 1의 개수를 저장해주는 vector를 정의한다.
• fibonacci(0)은 0만 하나 출력해주므로 1 0이 된다. 마찬가지로 fibonacci(1)은 1만 하나 출력해주므로 0 1이 된다.
• fibonacci(2) = fibonacci(1) + fibonacci(0)이므로 1 1을 출력하게 된다. 즉 fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)이므로 fibonacci(N)의 0과 1의 개수는 fibonacci(N-1)과 fibonacci(N-2)의 0과 1의 개수의 합이 된다.
• 동적 프로그래밍을 이용해 반복하여 준다.

소스코드

//
//  FibonacciFunction.cpp
//  test
//
//  Created by 신기열 on 11/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main() {
    
    vector > v;
    int n;
    
    v.resize(40);
    
    v[0].first = 1; v[0].second = 0;
    v[1].first = 0; v[1].second = 1;
    
    for(int i = 2; i < 41; i++){
        v[i].first = v[i - 1].first + v[i - 2].first;
        v[i].second = v[i - 1].second + v[i - 2].second;
    }
    
    cin >> n;
    int buf[n];
    
    for(int i = 0; i < n; i++){
        cin >> buf[i];
    }
    
    for(int i = 0; i < n; i++){
        cout << v[buf[i]].first << " " << v[buf[i]].second << '\n';
    }
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/DP/FibonacciFunction.cpp