백준
백준 소스코드 [C++] 10826 피보나치 수 4
Hani_Levenshtein
2020. 10. 30. 17:55
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가
www.acmicpc.net
백준 소스코드 [C++] 10826 피보나치 수 4
#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;
}