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

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

10757번: 큰 수 A+B

 

1. 문제

---

💡  문제

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

💡 입력

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

💡 출력

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

 

 

2. 풀이

---

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

int main(){
    int* result;
    int A_Len, B_Len, result_Len, i, j, A_Temp, B_Temp, temp;
    char A_Num[10001] = {0,};
    char B_Num[10001] = {0,};
    
    A_Temp = B_Temp = temp = 0;
    result_Len = 1;
    
    scanf("%s %s", A_Num, B_Num);

    A_Len = strlen(A_Num);
    B_Len = strlen(B_Num);

    if (A_Len > B_Len){
        temp = A_Len;
        result_Len += A_Len;
        B_Temp = A_Len - B_Len;
    }
    else if (B_Len > A_Len){
        temp = B_Len;
        result_Len += B_Len;
        A_Temp = B_Len - A_Len; 
    }
    else{
        result_Len += A_Len;
        temp = A_Len;
    }

    result = (int*) malloc(sizeof(int) * result_Len);
    if (result == NULL) exit(1);
    memset(result, 0, sizeof(int) * result_Len);

    for (i = temp - 1 ; i >= 0 ; i--){
        if ((i - A_Temp) >= 0 && (i - B_Temp) >= 0) result[i + 1] += ((A_Num[i - A_Temp] + B_Num[i - B_Temp]) - ('0' * 2));
        else if (A_Temp != 0) result[i + 1] += (B_Num[i] - '0');
        else if (B_Temp != 0) result[i + 1] += (A_Num[i] - '0');

        if (result[i + 1] >= 10){
            result[i + 1] %= 10;
            result[i] += 1;
        }
    }

    for (i = 0 ; i < result_Len ; i++){
        if (result[i] != 0){
            j = i;
            break;
        }
    }

    for (i = j ; i < result_Len ; i++) printf("%d", result[i]);

    free(result);
}​

 

 

3. 메모

---

 문제에서 10의 10,000승까지의 숫자가 주어진다고 했다. 이는 우리가 흔히 사용하는 int형 변수에 담기 힘들다는 뜻과 같다. 그럼 어떻게 해야 할까? 바로 배열이라는 것을 사용하는 것이다..! 두둥-

 10,000자리까지 숫자를 받아와야 하니 char형 배열을 10001개 만들어주고 0으로 초기화했다.

#include <stdio.h>
#include <string.h> // strlen() 함수를 사용하기 위한 헤더 파일
#include <stdlib.h> // malloc(), memset() 함수를 사용하기 위한 헤더 파일

int main(){
    int* result; // 동적할당을 해줄 int형 포인터 변수 result
    int A_Len, B_Len, // 배열 A와 B의 길이를 담아줄 변수
    result_Len, // 결과값 배열 변수의 길이
    i, j, A_Temp, B_Temp, temp;
    
    // 문제에서 10,000자리의 숫자까지 받아야 한다고 했으니 10,000 + 마지막 널문자 '\0'까지 해서
    // 10,001개의 인덱스를 가진 char형 배열을 만들어주자.
    char A_Num[10001] = {0,};
    char B_Num[10001] = {0,};
    
    A_Temp = B_Temp = temp = 0;
    
    // 결과값 배열 길이는 배열 A, B의 길이에 1을 더한 값보다 클 수 없다.
    result_Len = 1;
    
    // 각각의 배열 첫 시작 주소에 값을 넣어준다.
    scanf("%s %s", A_Num, B_Num);

	// 각각의 배열의 길이를 구해준다. 동적할당을 통해 결과값 배열을 만들어 줄 것인데
    // A + B의 길이는 둘 중 가장 긴 배열의 길이에 1을 더한 값을 최대값으로 가지기 때문이다.
    A_Len = strlen(A_Num);
    B_Len = strlen(B_Num);

	// A가 B보다 길다면
    if (A_Len > B_Len){
    	// for문을 통해 배열 인덱스를 참조할 때, B 배열이 끝나도 A 배열 값을 결과값 배열에 넣어줘야 하기에
        // temp 값에 A 배열의 길이를 넣어준다.
        temp = A_Len;
        
        // 결과값 길이는 A_Len + 1
        result_Len += A_Len;
        
        // 배열 A와 B의 길이가 다르다면 인덱스를 참조할 때 다른 자리수를 가르키기 때문에
        // B_Temp를 통해 자리수를 맞춰준다.
        B_Temp = A_Len - B_Len;
    }
    else if (B_Len > A_Len){
        temp = B_Len;
        result_Len += B_Len;
        A_Temp = B_Len - A_Len; 
    }
    else{
        result_Len += A_Len;
        temp = A_Len;
    }
    
    ~

---

 산식은 단순하다. 먼저 각 배열의 끝자리를 더해야 하는데, 두 배열의 길이가 같다면 for문을 통해 해당 인덱스의 값을 서로 더해주고 앞자리에 1을 더해주면 된다. 하지만 두 배열의 길이가 다르다면? 이때 앞서 구해둔 A_Temp와 B_Temp를 사용한다.

 

 A_Temp가 있다면 배열 A의 길이가 배열 B보다 A_Temp만큼 짧다는 의미이기에, 그 값만큼 짧은 배열 인덱스에서 빼준다. 예를 들어, 배열 A은 인덱스 5, 배열 B는 인덱스 3이라고 가정하자. 변수 A_Temp, B_Temp는 각각 0과 2 값을 가질 것이고, 동적할당한 result은 A와 B, 두 배열 중 가장 긴 배열의 길이 + 1을 최대값으로 가지기에 인덱스가 6인 배열이 된다.

 

for (i = temp - 1 ; i >= 0 ; i--){
    if ((i - A_Temp) >= 0 && (i - B_Temp) >= 0){
    	result[i + 1] += ((A_Num[i - A_Temp] + B_Num[i - B_Temp]) - ('0' * 2));
        
        ~

A : 5
B : 3
temp : 5
A_Temp : 0
B_Temp : 2
        
for (i = 5 - 1 ; i >= 0 ; i--){
    if ((i - 0) >= 0 && (i - 2) >= 0){
    	result[i + 1] += ((A_Num[ i ] + B_Num[ i - 2 ]) - ('0' * 2));
        
        ~

 

 배열 B의 인덱스를 체크할 때 i에서 B_Temp를 빼주면 A_Num[4]와 B_Num[2]를 체크하기에 배열이지만 숫자처럼 끝자리를 맞출 수 있다. '0' 값을 빼준 것은 우리가 값을 받아올 때, 문자열로 받아왔기 때문인데 문자 '0'은 아스키 코드값 48이기에 48 - 48 = 0 과정을 통해 문자를 정수로 변환할 수 있다.

 

 쭉 계산하다보면 언젠가 '(i - A_Temp) >= 0 && (i - B_Temp) >= 0' 조건문을 충족하지 않게 되는데, 이것은 곧 짧은 배열의 인덱스 0번까지 참조하고 이제 더 이상 남은 숫자가 없다는 뜻이다. 그렇다면 긴 배열의 남은 인덱스 값들을 그대로 결과값 배열에 옮겨주면 된다.

 

    ~
    
    result = (int*) malloc(sizeof(int) * result_Len);
    if (result == NULL) exit(1);
    memset(result, 0, sizeof(int) * result_Len);

    for (i = temp - 1 ; i >= 0 ; i--){
        if ((i - A_Temp) >= 0 && (i - B_Temp) >= 0)
        	result[i + 1] += ((A_Num[i - A_Temp] + B_Num[i - B_Temp]) - ('0' * 2));
        else if (A_Temp != 0) result[i + 1] += (B_Num[i] - '0');
        else if (B_Temp != 0) result[i + 1] += (A_Num[i] - '0');

        if (result[i + 1] >= 10){
            result[i + 1] %= 10;
            result[i] += 1;
        }
    }

    for (i = 0 ; i < result_Len ; i++){
        if (result[i] != 0){
            j = i;
            break;
        }
    }

    for (i = j ; i < result_Len ; i++) printf("%d", result[i]);

    free(result);
}

 

 만일 마지막 인덱스 값의 합이 10을 넘지 않는다면 결과값을 출력할 때, 000011 이런 식으로 앞에 0이 붙게 된다. 'result[i] != 0'을 체크해서 결과값을 출력하는 for문의 i를 조정해주면 된다.

 

 정말 뇌가 아픈, 너무너무 재밌는 문제였다 ㅎㅅㅎ