티스토리 뷰

백준

백준 소스코드 [C++] 4150 피보나치 수

Hani_Levenshtein 2020. 10. 30. 18:25

www.acmicpc.net/problem/4150

 

4150번: 피보나치 수

피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력

www.acmicpc.net

백준 소스코드 [C++] 4150 피보나치 수

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
string add(string a, string b) {
    int sum = 0;
    string res;
    while (!a.empty() || !b.empty() || sum) {
        if (!a.empty()) sum += a.back() - '0', a.pop_back();
        if (!b.empty()) sum += b.back() - '0', b.pop_back();
        res.push_back((sum % 10) + '0');
        sum /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    string first = "0", second = "1", res = "1";
    for (int i = 1;i < n;i++) {
        res = add(first, second);
        first = second;
        second = res;
    }
    if (n == 0) cout << "0" << '\n';
    else cout << res << '\n';

    return 0;
}
댓글