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

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

우선 바로 생각나는 방식은 DP를 활용하면서 long long 형 변수를 사용하는 방식이였다.

하지만 이와 같은 방식으로 해결하려 하면 숫자가 너무 커져서 해결할수가 없다.

따라서 string을 사용하는 방식으로 변경해야 한다.

 

두 string을 더하는 함수가 핵심이다.

string sum(string a, string b){
    int num = 0;
    int carry = 0;
    string result = "";

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    while(a.length() < b.length()){
        a += "0";
    }

    while(a.length() > b.length()){
        b += "0";
    }

    for(int i = 0; i < a.length(); i++){
        num = ((a[i] - '0') + (b[i] - '0') + carry) % 10;
        result += to_string(num);
        carry = ((a[i] - '0') + (b[i] - '0') + carry) / 10;
    }
    if(carry != 0){
        result += to_string(carry);
    }

    reverse(result.begin(), result.end());
    return result;
}

우선 받은 String을 reverse로 뒤집어야 한다. 뒤집어야 for문을 돌때 1의 자리부터 더할 수 있다.

그 다음으로는 두 string의 길이를 맞춰야 한다.

 

예를 들어 보자. "10000" 과 "100"을 더하려면 우선 자리의 숫자부터 통일시켜야 한다.

따라서 뒤집은 "00001" 과 "001' 에서 길이를 맞추면

"00001" 과 "00100" 이 된다. 

 

이제 이 두 String을 더하면 된다. carry라는 올림수 또한 생각해줘야 한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 10001

int N;
string DP[MAX];

string sum(string a, string b){
    int num = 0;
    int carry = 0;
    string result = "";

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    while(a.length() < b.length()){
        a += "0";
    }

    while(a.length() > b.length()){
        b += "0";
    }

    for(int i = 0; i < a.length(); i++){
        num = ((a[i] - '0') + (b[i] - '0') + carry) % 10;
        result += to_string(num);
        carry = ((a[i] - '0') + (b[i] - '0') + carry) / 10;
    }
    if(carry != 0){
        result += to_string(carry);
    }

    reverse(result.begin(), result.end());
    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    DP[0] = "0";
    DP[1] = "1";
    for(int i = 2; i <= N; i++){
        DP[i] = sum(DP[i-1], DP[i-2]);
    }
    cout << DP[N];

    return 0;
}