큰 수 A+B (2)

문제

두 양의 정수 A와 B가 주어졌을 때, A+B를 구하는 문제입니다. C++의 기본 정수 자료형인 long long은 최대 19자리(약 900경)까지만 표현할 수 있습니다. 하지만 이 문제에서는 최대 10,000자리까지의 숫자가 주어지므로 기본 자료형으로는 계산할 수 없습니다. 따라서 숫자를 **문자열(String)**로 입력받아 각 자릿수를 직접 더하는 방식을 사용해야 합니다.

• 입력: 첫째 줄에 A와 B가 공백을 사이에 두고 주어집니다. (0 < A, B < 10^10000)
• 출력: 첫째 줄에 A+B를 출력합니다.

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

풀이: 문자열 기반의 덧셈 구현

초등학교에서 덧셈을 배울 때처럼, 숫자의 일의 자리(문자열의 맨 뒷부분)부터 앞으로 이동하며 각 자릿수를 더해주고, 받아올림(Carry)이 발생하면 다음 자릿수로 넘겨주는 방식으로 구현합니다.

1. 길이 비교 및 스왑: 덧셈 로직(addStr)을 하나로 깔끔하게 처리하기 위해, 항상 s1 문자열이 s2 문자열보다 길이가 길거나 같도록 위치를 바꿉니다(swap).
2. 뒤에서부터 덧셈 수행: 긴 문자열(s1)의 길이만큼 반복문을 돕니다. 인덱스를 조작하여 문자열의 맨 뒤에서부터 숫자(a, b)를 꺼내 정수형으로 변환합니다. 이때 짧은 문자열(s2)은 인덱스 범위를 초과하지 않도록 검사하여, 초과한 자리는 0으로 처리합니다.
3. 받아올림(Carry) 처리: 각 자릿수 a와 b, 그리고 아랫자리에서 넘어온 받아올림 값 c를 모두 더합니다(tmp). 현재 자릿수에 남을 값은 tmp % 10이 되며 이를 결과 문자열에 추가하고, 다음 자리로 넘어갈 받아올림 값은 tmp / 10으로 갱신합니다.
4. 결과 문자열 뒤집기: 일의 자리부터 결과 문자열에 추가했으므로, 완성된 문자열은 원래 숫자의 역순이 됩니다. 따라서 C++의 algorithm 헤더에 있는 reverse() 함수를 사용하여 문자열을 올바른 순서로 뒤집어 반환합니다.

코드 (C++)

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

// 두 큰 수(문자열)를 더하는 함수 (항상 s1의 길이가 s2보다 크거나 같다고 가정)
string addStr(string s1, string s2) {
    string ans = "";
    int c = 0; // 받아올림(Carry) 변수
    
    int len1 = s1.length();
    int len2 = s2.length();

    for (int i = 0; i < len1; i++) {
        // 긴 문자열의 뒤에서부터 숫자를 꺼냄
        int a = s1[len1 - i - 1] - '0';
        int b = 0;
        
        // 짧은 문자열의 인덱스 초과를 방지하며 뒤에서부터 숫자를 꺼냄
        if (i < len2) {
            b = s2[len2 - i - 1] - '0';
        }
        
        int tmp = a + b + c;
        ans += to_string(tmp % 10); // 현재 자릿수의 나머지 저장
        c = tmp / 10;               // 다음 자리로 넘어갈 받아올림 갱신
    }

    // 제일 높은 자릿수에서 받아올림이 남은 경우 처리
    if (c != 0) {
        ans += to_string(c);
    }

    // 일의 자리부터 추가했으므로 역순으로 뒤집어줌
    reverse(ans.begin(), ans.end());
    
    return ans;
}

int main() {
    // C++ 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s1, s2;
    cin >> s1 >> s2;

    // 항상 s1이 s2보다 길거나 같도록 조정 (기존 코드 논리 오류 보완)
    if (s1.length() < s2.length()) {
        swap(s1, s2);
    }

    cout << addStr(s1, s2) << "\n";

    return 0;
}

알고리즘 분류

수학, 문자열 처리, 임의 정밀도 / 큰 수 연산