[알고리즘] 백준 8437 - Julka (C++)

[문제 링크] : https://www.acmicpc.net/problem/8437

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

string remove(string s){
    int idx = s.size();

    for(int i=0; i<s.size(); i++){
        if(s[i] != '0'){
            idx = i;
            break;
        }
    }

    if(idx == s.size()){
        return "0";
    }

    return s.substr(idx);
}

string add(string s1, string s2){
    string s(max(s1.size(), s2.size()), '0');

    bool c = false;

    for(int i=0; i<s.size(); i++){
        int tmp = c;
        c = false;

        if(i < s1.size()){
            tmp += s1[s1.size() - i - 1] - '0';
        }
        if(i < s2.size()){
            tmp += s2[s2.size() - i - 1] - '0';
        }
        if(tmp >= 10){
            c = true;
            tmp -= 10;
        }

        s[s.size() - i - 1] = tmp + '0';
    }

    if(c > 0){
        s.insert(s.begin(), '1');
    }

    return remove(s);
}

bool comp(string s1, string s2){
    if(s1.size() != s2.size()){
        return s1.size() > s2.size();
    }

    for(int i=0; i<s1.size(); i++){
        if(s1[i] == s2[i]){
            continue;
        }
        return s1[i] > s2[i];
    }

    return true;
}

string sub(string s1, string s2){
    if(comp(s1, s2) == false){
        swap(s1, s2);
    }

    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());

    string s = s1;
    int c = 0;

    for(int i=0; i<s.size(); i++){
        int cnt = c;
        c = 0;

        int tmp = (s1[i] - '0') - cnt;

        if(tmp < 0){
            c = 1;
            tmp += 10;
        }

        if(i < s2.size()){
            tmp -= (s2[i] - '0');
            if(tmp < 0){
                c = 1;
                tmp += 10;
            }
        }
        s[i] = tmp + '0';
    }

    if(c > 0){
        int d = s[s.size() - 1];
        d--;

        s[s.size() - 1] = d + '0';
    }

    reverse(s.begin(), s.end());

    return remove(s);
}

string divide(string s){
    string res;
    int idx = 0, num = 0, cnt = 0;
    bool flag = false;

    while(idx != s.size()){
        int num = s[idx] - '0';

        switch(num){
        case 0:
            res += '0';
            idx++;
            break;
        case 1:
            num = num * 10 + s[idx + 1] - '0';
            cnt = num / 2;
            
            if(flag == false){
                res += '0';
            }
            else{
                flag = false;
            }

            res += cnt + '0';
            num -= (cnt * 2);
            s[++idx] = num + '0';

            if(num % 2 == 0){
                idx++;
            }
            else{
                flag = true;
            }
            break;
        default:
            cnt = num / 2;
            res += (num / 2) + '0';
            num -= cnt * 2;
            s[idx] = num + '0';

            if(s[idx] == '0'){
                idx++;
            }
            else{
                flag = true;
            }
        }
    }

    return remove(res);
}

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

    string A, B;
    cin >> A >> B;

    string res = sub(A, B);
    string res1 = divide(res);
    string res2 = add(res1, B);

    cout << res2 << "\n" << res1 << "\n";

    return 0;
}