[구현 / BOJ 15353 / C++] 큰 수 A+B (2)

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

15353번: 큰 수 A+B (2)

1) 일반적인 더하기가 불가능하니 BigInt 혹은 String으로 덧셈을 구현한다.

숫자를 잘 보자. A,B의 최대값이  10의 10000승이다!!

 

덧셈을 직접 구현해주면 된다. 이런 문제를 풀때마다 뭔가 현타가 가끔씩 온다. 

아이디어가 생각나지 않으면 "하.... 이게 뭐야.... 나는 덧셈 뺄셈도 못하는 사람이었네... " 하면서 말이다

 

덧셈의 원리를 생각하면서 문제를 해결하면 된다.

 

5+8에서 올림수는 1이고, 남아있는 수는 3이므로, 5+8은 13이 된다.

14 + 19에서 4+9, 1+1을 순서대로 진행하고, 만약 올림수가 발생할 경우 이 올림수를 다음의 연산에 넘겨준다.

즉, 4+9=13 => 13%10=3, 13/10=1 => 남아있는 수는 3, 올림수는 1 => (1) + 1 + 1 = 3 

총 "3"+"3" = "33" 이다.

 

나는 재귀적으로 해결했는데, 고생한 부분이 있다면 2개의 자리수가 같을때는 매우 쉽지만 자리수가 다를 때는 약간의 생각이 필요하다!!

나는 이 부분을 못찾아 고생했는데, 그냥 빈자리수를 0으로 채워넣어버리면 된다. 혹은, string의 reverse 함수를 활용해서 index[0]부터 계산해나가고, 최종 결과에 reverse를 해주는 방법도 있다!

 

#include <bits/stdc++.h>

using namespace std;
string A, B;
string total="";
int mx, mn;

void go(int here, int carry){
    if(here == -1) {
        if(carry) total = to_string(carry) + total;
        
        return;
        
    }
    
    int res = (A[here]-'0') + (B[here]-'0') + carry;
    
    if(res >= 10) {
        total = to_string(res-10) + total;
        go(here-1, res/10);
    } else{
        total = to_string(res) + total;
        go(here-1, 0);
    }

    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> A >> B;
    mx = max((int)A.length(), (int)B.length());
    mn = min((int)A.length(), (int)B.length());
    
    if((int)A.length()!=(int)B.length()){
       
        
        if((int)A.length() > (int)B.length()){
            for(int i = 0 ; i < mx-mn ; i++){
                B = "0" + B;
            }
        }else if((int)A.length() < (int)B.length()){
            for(int i = 0 ; i < mx-mn ; i++){
                A = "0" + A;
            }
        }
    }
    
    go(mx-1,0);
    
    cout << total;
    
    
}