[10826번]피보나치 수 4

www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

피보나치 수의 범위가 long long 범위를 초과하므로, string을 이용하여 풀어야합니다.

 

점화식

dp[i] = dp[i-1] + dp[i-2]

 

string 덧셈

길이가 짧은 문자열 앞쪽에 '0'을 추가하여 두 문자열의 길이를 같게 만들어 준 뒤 덧셈연산을 수행하였고

10이상이면 carry를 하나 늘리고 다음자릿수 계산에서 carry가 있으면 1더해주도록 했습니다.

계산 종료 후 남아있는 carry가 있으면 '1'을 추가하여 자릿수를 늘려주었습니다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string str_sum(string s1, string s2){
    string mi = s2, ma = s1;
    string s = "";
    int carry = 0;

    //짧은 문자열 앞에 '0'을 붙여서 긴문자열과 같은 길이로 만듬
    for(int i = 0; i<s1.length()-s2.length(); i++){
        mi = '0'+ mi;
    }

    for(int i = ma.length()-1;i>=0;  i--){
        int num = 0;
        mi[i] = mi[i]-'0';
        ma[i] = ma[i]-'0';

        if(carry > 0){
            carry -= 1;
            num += 1;
        }

        num += ma[i]+mi[i];

        if(num>=10) {
            carry += 1;
            num -= 10;
        }

        s += (num + '0');
    }
    //연산 종료후 carry가 남아있으면 자릿수 하나 추가
    if(carry>0){
        s += '1';
    }
    reverse(s.begin(), s.end());
    return s;
}

int main(){

    int n;
    cin>>n;

    string dp[10001];
    dp[0] = "0";
    dp[1] = "1";

    for(int i = 2; i<=n; i++){
        dp[i] = str_sum(dp[i-1],dp[i-2]);
    }

    cout<<dp[n];
}