백준 알고리즘 10757번 큰 수 A+B (C언어)

브론즈Ⅴ

 

 

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

10757번: 큰 수 A+B

 

 

풀이 방법

C언어로 표현할 수 있는 최대 정수는 자료형 unsigned long long을 이용한 18,446,744,073,709,551,615(약 10^19) 승이다. 하지만, 이 문제의 경우 A와 B의 최댓값이 10^10000-1이기 때문에 unsigned long long을 사용하기에는 부적절하다. 따라서 컴퓨터 내에서 실제로 덧셈을 하는 것이 아닌, 우리가 덧셈을 하는 과정을 이용해 실제 덧셈을 하는 것처럼 코드를 작성해야한다. 즉, 아래의 예시와 같은 과정을 직접 코드로 구현해 주어야 한다.

받아올림		+1
A	2	0	8
B	5	5	7
+	-------------------	-------------------	-------------------
	7	6	5

 

 

 

내 코드

반응형

#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
 
void Reverse(char str[], int len); //배열을 역순으로 뒤집는 함수
 
int main() {
    
    char A[10001], B[10001], C[10002];
    int i, AN, BN, CN, temp, carry = 0, pA, pB;
 
    scanf("%s %s", &A, &B);
 
    AN = strlen(A);
    BN = strlen(B);
 
    Reverse(A, AN);
    Reverse(B, BN);
 
    for (i = 0; i < AN || i < BN; ++i) {
        if (!(A[i] >= '0' && A[i] <= '9'))
            pA = 0;
        else
            pA = A[i] - '0';
        if (!(B[i] >= '0' && B[i] <= '9'))
            pB = 0;
        else
            pB = B[i] - '0';
        temp = pA + pB + carry;
        //받아올림이 있는 경우
        if (temp >= 10) {
            C[i] = (temp % 10) + '0';
            carry = 1;
        }
        //받아올림이 없는 경우
        else {
            C[i] = temp + '0';
            carry = 0;
        }
    }
    //받아올림이 있는 경우
    if (carry == 1) {
        C[i] = '1';
        C[i + 1] = '\0';
        CN = i + 1;
    }
    //받아올림이 는 경우
    else {
        C[i] = '\0';
        CN = i;
    }
 
    Reverse(C, CN);
 
    printf("%s\n", C);
    
    return 0;
}
 
void Reverse(char str[], int len) {
    int i;
    char temp;
 
    for (i = 0; i < len / 2; ++i) {
        temp = str[i];
        str[i] = str[len - i-1];
        str[len - i - 1] = temp;
    }
}
 

 

 

코드설명

1   | scanf 함수를 사용할 때 경고창을 띄우지 않도록 하는 전처리 지시문이다.

2   | scanf, printf 함수를 사용하기 위한 전처리 지시문이다.

3   | strlen 함수를 사용하기 위한 전처리 지시문이다.

5   | 배열을 역순으로 뒤집는 함수를 사용하기 위해 선언하였다. (60~69)

9   | 입력 받을 A, B와 출력할 C를 char형 배열로 선언하였다. 여기서 A의 최대값이 10^10000-1, B의 최대값이 10^100001,

       C의 최대값이 약 10^10001 이므로 각 배열의 크기를 10001, 10001, 10002로 선언하였다. 

10 |  각각의 변수를 다음의 용도로 정의하였다.

        // i : for문에서 사용하기 위해

        // AN, BN, CN : char형 배열 A, B, C의 크기가 몇인지(각각 몇자리 수 인지)를 확인하고 저장하기 위해

        // temp: n자리의 A와 n자리의 B의 합이 10이상일 경우(받아올림을 해야할 경우)를 위해 A와 B의 합을 임시로 저장하                       기 위해

        // carry : 받아올림(덧셈이니 0 or 1)이 있을 경우 1, 없을 경우 0을 다음 자리수에 더해주기 위해

        // pA, pB : temp에 최종적으로 더해줄 A의 값과 B의 값을 저장하기 위해(A와 B의 자릿수가 다를 경우를 위해)

12 |  A와 B의 값을 각각 문자열로 입력받기 위한 코드이다.

14, 15 | 문자열 A와 B의 크기를 입력받아 각각 AN과 BN에 저장하기 위한 코드이다.

17, 18 | 덧셈과 반올림을 편리하게 하기위해 문자열 A와 B를 반대로 뒤집기 위한 코드이다. ex) 12345 -> 54321

20 | 문자열 A와 B를 뒤집어 놓았기 때문에 A와 B 모두 1의 자리 숫자가 index 0번에 오게 된다. 따라서 i를 index 0부터(1의

       자리부터) 문자열 A와 B의 마지막 index까지(마지막 자릿수까지) 따라가도록 하는 코드이다.

21 ~ 28 | A or B의 i번째 인덱스 값이 0~9일 경우 pA or pB에 A or B의 i번째 인덱스에 있는 값을 대입하고, 0~9가 아닐 경우

              (이 경우 A와 B의 자릿수가 달라 둘 중 한가지가 마지막 인덱스를 이미 지났을 경우) pA or pB에 0을 대입하는 코

               드이다.

              *이후 코드의 덧셈을 위해 pA와 pB를 정수형 변수로 선언했으므로, A와 B의 i번째 인덱스에 있는 char형 값에 문

               자 '0'을 빼주어 int형으로 형변환 한 후, pA와 pB에 대입해준다.

29 | A와 B의 값을 임시로 저장할 변수 temp에 pA, pB, 받아올림 값을 위한 carry 변수를 더해주는 코드이다.

30 ~ 34 | temp의 값(pA+pB+carry 값)이 10보다 큰 경우(받아올림이 필요할 경우) C의 i번째 index에 있는 값에 temp%10

               의 값을 char형으로 형변환 한 후 저장하고 1을 받아올림 하기위해 carry에 1을 저장한다.

35 ~ 39 | temp의 값(pA+pB+carry 값)이 10보다 작은 경우(받아올림이 필요없는 경우) C의 i번째 index에 있는 값에 temp

              를 char형으로 형변환한 값을 저장하고 받아올림할 값이 없다는 것을 전달하기 위해 carry에 0을 저장한다.

41 ~ 46 | carry의 값이 1일 경우(받아올림할 값이 있는 경우) C의 i번째 index에 '1'(carry의 값 1의 char형 형태)을 저장하고

               i+1번 index에 '\0'(문자열의 끝을 나타내는 null문자)를 대입한다. 또한, CN에 문자열 C의 크기인 i+1을 저장한다.

47 ~ 51 | carry의 값이 0일 경우(받아올림할 값이 없는 경우) C의 i번째 index에 '\0'(문자열의 끝을 나타내는 null문자)를 대

              입한다. 또한, CN에 문자열 C의 크기인 i을 저장한다.

53 | 마지막자리수 -> 1의 자리수의 형태로 되어있는 C를 1의 자리수 -> 마지막자리수의 형태로 바꾸기 위해 Reverse함수

       를 사용하는 코드이다.

55 | C를 출력하는 코드이다. 

60~69 | 배열의 첫번째와 마지막 값 교환, 배열의 두번째와 마지막에서 두번째 값 교환, 배열의 세번째와 마지막에서 세번

             째 값 교환 ... 의 과정을 반복하여 배열을 뒤집는 함수이다.

 

 

 

느낀점

 

- 문제의 예제 입출력만을 보고 처음에는 unsigned long long을 이용해 문제를 풀다가 당연하게도 풀리지 않아서 입력에 나와있는 입력값의 범위를 보고 그제서야 문제를 어떻게 풀어야 할지를 생각하게 되었다. 다음부턴 문제를 더 꼼꼼히 보고 풀어야 할 것 같다.

- 원래라면 swap함수도 만들어서 사용했을 것이지만 이런 문제를 풀때는 굳이 사용하지 않았다.

- A와 B의 자리수가 다른 경우( ex) A는 10자리의 수인데 B는 8자리인 경우 ) 를 생각하며 코드를 작성해야 한다.