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

백준 웹사이트 "10757번 - 큰 수 A+B" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10757번: 큰 수 A+B

---

소스 코드

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

int main(void){
    // long long int 최댓값: 2^63-1 = 9223372036854775807
    // A, B의 최댓값: 10^10000
    // 따라서 A, B를 문자열로 받고, 일의 자리부터 덧셈을 진행한다는 아이디어

    char A_str [10002]; //10^10000은 최대 10001자리, \0을 위한 1자리
    char B_str [10002];
    scanf("%s %s", A_str, B_str);
    int A_len = strlen(A_str);
    int B_len = strlen(B_str);

    int min_len, max_len;
    if(A_len < B_len){
        min_len = A_len;
        max_len = B_len;
    }
    else{
        min_len = B_len;
        max_len = A_len;
    }
    //printf("max_len: %d, min_len: %d\n", max_len, min_len);

    // A, B, sum 선언
    int A[10002];
    int B[10002];
    for(int count=0; count<10002; count++){
        A[count] = A_str[count]-'0';
        B[count] = B_str[count]-'0';
    }

    int sum [max_len];
    for(int num=0; num<max_len; num++){
        sum[num] = 0;
    }

    // 덧셈 진행
    for(int i=0; i<min_len; i++){
        int a = A[A_len-1-i];
        int b = B[B_len-1-i];
        //printf("a: %d, b: %d\n", a, b);

        int digit = (sum[i]+a+b)%10;
        int overflow=0;
        if(sum[i]+a+b>=10)
            overflow=1;
        
        sum[i] = digit;
        if(min_len==max_len && i==min_len-1){ // i+1이 존재하지 않을 수 있음
            sum[i] += overflow*10; // 이 경우에만 두 자릿수를 저장
        }
        else{
            sum[i+1] += overflow;
        }
        //printf("%d\n", sum[i]);
    }

    // max_len - min_len 부분 덧셈
    for(int j=min_len; j<max_len; j++){ //min_len == max_len일 경우 제외
        if(A_len < B_len){
            sum[j]+=B[max_len-1-j];
        }  
        else
            sum[j]+=A[max_len-1-j];

        if(sum[j]>=10 && j!=max_len-1){
            sum[j]=sum[j]%10;
            sum[j+1]+=1;
        }
    }

    // 'sum'을 역순으로 출력
    for(int k=0; k<max_len; k++){
        printf("%d", sum[max_len-1-k]);
    }
}

---

문제 풀이

  C/C++언어를 위한 문제라고도 할 수 있습니다. 파이썬과 같이 high-level한 언어는 10,000 자리의 정수까지도 비교적 자유롭게 다룰 수 있지만, C/C++ 언어는 원초적이기에 제약이 많습니다. C언어에서 'int'의 최댓값은 2^31-1이고, 이보다 높은 정수를 사용하기 위한 'long long int'의 최댓값도 2^63-1입니다. 2^63-1은 9223372036854775807으로, 당연히 10^10000보다는 훨씬 작습니다. 그렇다면 C언어에서 이렇게 큰 수의 덧셈은 어떻게 해야할까요? 정답은 '배열'에 있습니다.

  전체적인 아이디어부터 설명드리면, 두 정수 A, B를 우선 문자열로 입력받습니다. C언어에서 문자열은 'char'의 배열이기에, 한 배열 요소(element) 안에 한 숫자씩 들어가게 됩니다. 이러한 char 배열을 그대로 int 배열로 바꾼 후, 일의 자리에 해당하는 숫자들부터 차례로 덧셈을 진행하면, 큰 수의 합도 결국 배열로 표현이 가능합니다.

  Line 9 ~ 23은 A, B를 입력 받고 두 수의 길이를 계산 및 비교하는 과정입니다. 10^10000은 최대 10001자리이며, 문자열의 마지막은 '\0'을 통해 표시해야 하므로, 문자열 A와 B의 크기를 10002로 선언합니다.

  Line 27 ~ 37에서는 문자열 A, B를 정수 배열로 전환하고, 두 수의 합을 저장하기 위한 새로운 배열 'sum'을 선언합니다. '전환'한다고 표현했지만, 사실 새로운 int 배열을 선언한 뒤, 문자열의 요소를 하나씩 옮기는 과정입니다. 이때 그대로 옮기면 각 숫자의 아스키 코드로 옮겨지므로, '0'의 아스키 코드만큼씩 빼주는 방식으로 옮깁니다.

  Line 40 ~ 58에서 드디어 덧셈을 진행합니다. 처음 초등학교에서 덧셈을 배울 때, 일의 자리끼리 더한 후 10 이상이면 1을 위에 기록하고, 십의 자리끼리 더하고했던 과정이 기억나시나요? 이 문제에서도 초심으로 돌아가, 한 자리씩 차분히 더해줍니다. 일의 자리끼리 더하고, 만약 10 이상이면 'overflow' 변수를 1로 바꿔 표시해줍니다. i번째 자리에서 생긴 overflow는 'sum[i+1]'에 기록되어, 다음 i+1번째 자리를 계산할 때 반영됩니다. 이러한 과정을 반복하고, 마지막 배열 요소일때만 두 자릿수가 된다면 두 자릿수를 그대로 저장합니다.

  두 수의 길이가 같다면 여기서 풀이를 끝낼 수 있습니다. 하지만 그렇다는 보장이 없기에, Line 61 ~ 72에서 길이가 다른 경우 마저 계산합니다. 이는 A와 B 중에서 더 큰 수의 남은 자리들을 복사하는 과정이며, overflow가 일어나는 경우만 추가로 고려해줍니다 (Line 68 ~ 71).

  마지막으로 sum 배열을 출력합니다. 인덱스 0에는 가장 높은 자릿수가, 마지막 인덱스에는 가장 낮은 일의 자릿수가 저장되어 있기에, 역순으로 출력을 진행합니다 (Line 75 ~ 77). 예제 9223372036854775807 9223372036854775808과 같은 두 숫자를 입력했을 때 성공적으로 합이 계산되는 것을 보면, 꽤나 뿌듯합니다. 다만, 입력된 두 수의 길이가 다를 경우도 꼭 한 번 확인해보세요!