[C] 백준 10757번 / 큰 수 A + B

**문제**
두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

**입력**
첫째 줄에 A와 B가 주어진다. (0 < A,B < 10^10000)

**출력**
첫째 줄에 A+B를 출력한다.

**예제 입력 1**
9223372036854775807 9223372036854775808
**예제 출력 1**
18446744073709551615

파이썬 같은 언어는 10,000자리 정도의 자연수도 자유롭게 다룰 수 있습니다. 하지만 C/C++이라면 이 문제를 어떻게 풀까요? C/C++ 사용자가 아니더라도 고민해 보면 좋을 것입니다. 파이썬을 사용하면 쉽게 풀 수 있는 문제이지만 C로 한번 풀어보겠다.

#include <stdio.h>

int main(void)
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", a + b);

    return 0;
}

위 문제를 C에서 간단하게 구현하면 위처럼 구현할 수 있지만, 예제 입력인 9223372036854775807 9223372036854775808를 넣으면 -2라는 기대하지 않은 결과가 출력된다. C에서는 int 자료형에 담을 수 있는 최대값이 2,147,483,647이기 때문에 최대값을 넘기는 수를 입력했기 때문에 오버플로우가 발생한 것이다.

위의 문제 때문에 C에서는 int 대신 문자열 배열을 이용하여 문자열끼리 더하는 알고리즘으로 구현해야한다.

---

A, B의 최대값은 10^10000 (10의 10000승)이다. 10^1은 10이고, 10^2는 100이다. 이와 같이 10의 지수가 1씩 증가할때마다 10의 배수가 1개씩 더 붙는다.

따라서 10^3은 1000, 10^4는 10000이 될 것이다. 이런 규칙에 따라 승에 따라서 각 자릿수를 구할 수 있다.

-> 각 승에 따라 +1을 하면 자릿수를 구할 수 있다는 것을 알 수 있음
10의 1승 -> 10 (2자리)
10의 2승 -> 100 (3자리)
10의 3승 -> 1000 (4자리)
10의 10000승 -> .. (10001자리)

따라서 A, B의 최대 자리수는 10001 자리라는 것을 알 수 있다.

char A[10002] = {0};
char B[10002] = {0};
char res[10003] = {0};

10001 자리를 담을 수 있는 배열을 선언하려면 C에서는 문자열 배열의 크기를 결정할 때 NULL문자까지 고려해서 char형 배열의 마지막에는 NULL문자('\0')를 추가해야 하므로, 배열 크기를 10002로 지정한다.

배열을 선언할 때 {0}으로 초기화를 하면, 배열의 모든 요소를 0으로 초기화할 수 있다. 이렇게 초기화를 하면, 배열의 길이에 관계없이 모든 요소를 0으로 초기화할 수 있기 때문에, 예기치 않은 결과를 방지할 수 있다.

반면에, char A[10002];와 같이 배열을 초기화하지 않으면, 배열 요소에 이전에 사용되었던 값이 그대로 남아있을 수 있다. 이는 문제 해결에 영향을 끼칠 수 있으며, 예기치 않은 결과를 초래할 수 있다.

따라서, char A[10002] = {0};와 같이 배열을 초기화하는 것이 안전한 방법입니다. 이렇게 초기화를 하면, 배열의 모든 요소가 0으로 초기화되므로, 배열 요소에 이전에 사용되었던 값이 그대로 남아있을 가능성을 배제할 수 있다.

문자열을 더하는 경우, 두 문자열의 길이의 합보다 결과 문자열의 길이가 최소한 1만큼 더 커지게 되므로 결과값은 10003 크기의 배열로 선언한다.

문자열 배열에 들어있는 문자들을 자릿수대로 세로덧셈 방식대로 더해줄 건데, 세로 덧셈을 진행할 때 입력받은 숫자의 일의 자리부터 더해나가는 방식을 사용하기 때문에 역순으로 정렬된 입력값을 사용하면 일의 자리부터 차례대로 더해가면서, 다음 자리수에 올림수를 더해주기 용이해진다.

#include <stdio.h>
#include <string.h>

void reverse(char arr[])
{
    int len = strlen(arr);
    for (int i = 0; i < len / 2; i++)
    {
        char temp = arr[i];
        arr[i] = arr[len - 1 - i];
        arr[len - 1 - i] = temp;
    }
}

int main(void)
{
    char A[10002];
    char B[10002];
    char res[10003];
    int len;
    // 자릿수
    int carry = 0;

    scanf("%s%s", A, B);

    // 역순정렬을 위해 reverse 함수를 구현하고 A, B를 역순정렬한 후 시작한다.
    reverse(A);
    reverse(B);

    /*
    역순정렬된 배열에서 두 수 A, B를 더할때 둘 중 더 큰 자릿수대로
    덧셈이 이루어져야 하기 때문에 더 큰 배열의 크기를 len에 저장한다.
    */
    if (strlen(A) > strlen(B))
        len = strlen(A);
    else
        len = strlen(B);

    for (int i = 0; i < len; i++)
    {
        /*
        문자열 배열로 두 수를 받아왔으므로 배열을 순회할 때 문자열을 숫자로 바꾸고 계산한다.
        C에서는 문자의 ASCII 코드 값이 정수로 저장되어 있으므로
        48에 해당하는 '0'을 빼주면 정수값을 얻을 수 있다.
        */
        int sum = A[i] - '0' + B[i] - '0' + carry;

        /*
        sum이 0보다 작으면 하나가 null값이 들어가 마이너스 자리가
        되었다는 뜻이므로 0이 될때까지 '0'을 더해줘서 원래의 값으로 만들어준다.
        */
        while (sum < 0)
            sum += '0';
        // 만약 더한 수가 9를 넘어가면 자릿수를 하나 올려야한다.
        if (sum > 9)
            carry = 1;
        else
            carry = 0;

        // 더한 수를 10으로 나눈 나머지를 결과에 저장한다.
        res[i] = sum % 10 + '0';
    }
    // for문이 끝난 후 마지막 자리에서 받아올림 발생 시 배열의 마지막에 1추가
    if (carry == 1)
        res[len] = '1';

    reverse(res);

    printf("%s", res);

    return 0;
}

---

참고

• https://kiffblog.tistory.com/172
• https://abcdefgh123123.tistory.com/194