[백준 C++] 10826번 : 피보나치 수 4

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

10826번: 피보나치 수 4

풀이 :

- n번째 피보나치 수를 구하는 것으로, n의 최댓값이 10000이기 때문에 그냥 구하면 오버플로우가 난다

- 따라서 똑같이 dp 점화식을 세우되, 문자열의 배열을 만들어서 각 자리만 숫자로 변환해 계산해주었다

- 문자열이기 때문에 거꾸로 뒤집고, 둘의 길이를 맞춘 다음, 각 자리를 더해 10 이상인지를 확인하고,

   10 이상이라면 다음 수에 1을 더해줌으로 문자열에서의 덧셈을 할 수 있다

 

코드 :

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string get_num(string s1, string s2){
    int num, temp=0;
    string res;

    reverse(s1.begin(), s1.end()); //거꾸로 뒤집기
    reverse(s2.begin(), s2.end());

    while(s1.size() < s2.size()){ //둘의 사이즈를 맞추기 위해 
        s1 += '0'; //s1의 사이즈가 더 작다면 0으로 채워준다
    }
    while(s1.size() > s2.size()){
        s2 += '0';
    }
    for(int i=0; i<s1.size(); i++){
        num = (s1[i]-'0'+s2[i]-'0'+temp) % 10; //각 자리수를 더하고 10으로 나눈 나머지만 구해서 일의 자리만 더해준다
        res += to_string(num);
        temp = (s1[i]-'0'+s2[i]-'0'+temp) / 10; //둘을 더한 값이 10 이상이라면 temp에는 1이 대입되어,
    } //다음 자리 수를 계산할 때 1더해져서 계산이 된다
    if(temp != 0){ //마지막 값이 10 이상일 경우 고려
        res += to_string(temp);
    }
    reverse(res.begin(), res.end()); //구한 값을 다시 거꾸로 뒤집어 주고 리턴
    return(res);
}

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;
    string s[10010];

    cin >> n;

    s[0] = '0';
    s[1] = '1';

    for(int i=2; i<=n; i++){
        s[i] = get_num(s[i-1],s[i-2]); //피보나치의 점화식을 함수로 호출
    }
    cout << s[n] << '\n'; 
}