[c언어] 백준 10757. 큰 수 A + B

문제

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

입력

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

출력

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

구상

사람이 덧셈을 할 때 일반적으로 사용하는 세로 덧셈 방법을 사용할 것이다.

 

우선 숫자를 문자열로 받는다.

$10^{1}$은 두 자리, $10^{2}$은 세 자리... 이므로 $10^{10000}$은 10001 자리일 것이다. 이 정도 크기의 수를 담을 수 있는 문자열 배열을 만든다. res는 계산할 결과를 저장할 배열이다.

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

 

세로 덧셈을 할 때는 일의 자리 숫자부터 받아올림을 하며 계산해나간다.

이 과정을 편하게 진행할 수 있도록 입력받은 문자열을 reverse 함수를 통해 역순정렬한다.

 

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

 

12345와 1234를 더한다고 해보자.

 

역순정렬까지 마치면 이런 상태이다.

 

어느 자리 숫자까지 더해야 하는지는 큰 수가 결정한다. 큰 수의 자릿수만큼 덧셈이 이루어져야 한다.

더 큰 배열의 크기를 len에 저장해둔다.

 

int len = strlen(A) > strlen(B) ? strlen(A) : strlen(B);

 

이제 len만큼 각 자릿수를 더한다.

각 자리에는 0~9가 char로 저장되어 있다. 이 문자를 먼저 숫자로 변환해야 한다.

숫자 0의 아스키 코드는 48이다. 각 자리에 48을 빼고 int형으로 저장하면 문자를 숫자로 바꿀 수 있다. 문자끼리 뺄셈을 해도 같은 결과이다. 예를 들어 A - C는 -2이다. 

 

여기에 받아올림이 발생하면 1을 더해줘야 하므로 carry값도 함께 더한다. 

int sum = A[i] - '0' + B[i] - '0' + carry;

 

두 숫자의 덧셈이니 받아올림하는 수는 최대 1이다. 받아올림이 발생하면 carry는 1이고, 아니면 carry는 0이다.

 

if (sum > 9) carry = 1;
		else carry = 0;

 

이제 숫자를 다시 문자로 만들어서 res에 저장한다.

 

res[i] = sum % 10 + '0';

 

여기서 한 가지 문제가 발생하는데, A와 B 중 null이 있으면 sum값은 음수가 된다.

null값은 아스키코드 값이 0이고, 0은 48이기 때문이다.

 

 

A[0]와 B[0]의 합은

sum = 53 - 48 + 52 - 48 = 9가 되는데,

A[4] + B[4] = 49 - 48 +  0 - 48 = -47이 된다.

 

이 불필요한 뺄셈은 다시 '0'을 더해주어서 해결한다.

 

while (sum < 0) sum += '0';

 

정리하면 이렇다.

 

	for (i = 0; i < len; i++) {
		int sum = A[i] - '0' + B[i] - '0' + carry;
		while (sum < 0) sum += '0';
		if (sum > 9) carry = 1;
		else carry = 0;
		res[i] = sum % 10 + '0';
	}

 

덧셈이 모두 끝났으니 res를 역순정렬해서 원하는 결과로 복원해 출력한다.

코드

#include <stdio.h>
#include <stdlib.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 - i - 1];
		arr[len - i - 1] = temp;
	}
}

int main(void) {
	char A[10002] = { 0 }, B[10002] = { 0 }, res[10003] = { 0 };
	int carry = 0, i;	//carry는 받아올림

	scanf("%s%s", A, B);
	reverse(A);
	reverse(B);
	//더 긴 숫자의 길이 저장
	int len = strlen(A) > strlen(B) ? strlen(A) : strlen(B);

	for (i = 0; i < len; i++) {
		//숫자로 변환해 받아올림과 함께 더한다
		int sum = A[i] - '0' + B[i] - '0' + carry;
		//A[i] 또는 B[i]가 null인 경우 불필요한 뺄셈이 발생하므로
		//0 이상이 될 때까지 문자 0의 아스키 코드 값을 더한다
		while (sum < 0) sum += '0';
		if (sum > 9) carry = 1;	//받아올림
		else carry = 0;
		res[i] = sum % 10 + '0';	//받아올림 하고 남은 일의 자리 수의 아스키코드를 저장
	}
	if (carry == 1) res[len] = '1';	//가장 큰 자릿수에서 받아올림이 발생하면 배열의 마지막에 1을 추가
	reverse(res);	//덧셈이 완료되었으니 역순으로 정렬해 원하는 값으로 복원
	printf("%s", res);

	return 0;
}