피보나치 수 4 (feat. 백준, 10826번)

피보나치 수 4
https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string ans[10001]{""};
string findSum(string str1, string str2){
    // Before proceeding further, make sure length
    // of str2 is larger.
    if (str1.length() > str2.length())
        swap(str1, str2);
 
    // Take an empty string for storing result
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.length(), n2 = str2.length();
 
    // Reverse both of strings
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;
    for (int i=0; i<n1; i++)
    {
        // Do school mathematics, compute sum of
        // current digits and carry
        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
 
        // Calculate carry for next step
        carry = sum/10;
    }
 
    // Add remaining digits of larger number
    for (int i=n1; i<n2; i++)
    {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }
 
    // Add remaining carry
    if (carry)
        str.push_back(carry+'0');
 
    // reverse resultant string
    reverse(str.begin(), str.end());
 
    return str;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    ans[0] = "0", ans[1] = "1";
    register int N;
    cin >> N;
    for(register int i = 2; i <= N; ++i)
        ans[i] = findSum(ans[i - 2], ans[i - 1]);
    cout << ans[N];
	return 0;
}
// *&)*@*

 

반응형

피보나치 수열의 10000 까지의 값이라면 정수형으로 정의할 수 있는 64비트 자료형을 훨씬 넘게 됩니다.

따라서 string 으로 정수를 더하는 형태로 풀이해야 합니다.