[백준] 10757번 : 큰수 A+B

문제

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

입력

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

출력

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

예제 입력

9223372036854775807 9223372036854775808

예제 출력

18446744073709551615

알고리즘 [ 접근방법 ]

파이썬이나 자바같은 다른 언어를 사용해 풀었다면 굉장히 쉽게 풀 수 있는 문제이지만 내 주력언어인 C언어로는 상당히 생각할게 많은 문제였다. 문제에서 입력받는 A,B의 범위를 0 < A,B < 10¹⁰⁰⁰⁰ 로 설정했는데 C에서는 범위가 가장 넓은 자료형인 long long 마저도 +-10¹⁹ 까지만 커버가 가능하기 때문에 일반적인 숫자 자료형으로는 값을 입력받을 수 없다.

이때문에 숫자를 문자형으로 입력받고 아스키코드를 활용하는 방식으로 문제풀이를 구상했다.

10¹은 두자리, 10²은 세자리 … 이므로 10¹⁰⁰⁰⁰은 10001자리수 숫자를 의미한다. 따라서 이를 담을 수 있는 크기의 문자열을 설정해 주었다. 이때 10001자리수를 담기 위해서는 배열의 크기는 하나 더 큰 10002로 설정해줘야 한다. res는 최종 결과를 담을 문자열이다.

char arr1[10002] = { 0 }, arr2[10002] = { 0 }, res[10002] = { 0 };

보통 덧셈을 할때는 일의자리 부터 더한다음 합이 10이 넘어가면 다음자리에 1을 더해주는 방식으로 진행되는데 이를 구현하기 위해 문자열을 뒤집어주는 reverse함수를 만들었다.

void reverse(char *arr, int len) {
	char temp;

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

그리 어려운 코드는 아니지만 reverse함수는 어디에서나 쉽게 활용될 수 있으므로 기억해두는게 좋다.

다음으로 덧셈은 for문을 돌면서 자리마다 더해질 텐데 for문을 몇번 돌려야 할지 결정하는 기준은 입력받은 문자열의 자리수이다. 더 긴 자리수 만큼 for문이 실행되어야 하므로 이를 결정하기 위해 두 문자열중 어떤게 더 긴 문자열인지 판별하고 이를 저장해준다.

int len1 = strlen(arr1);
int len2 = strlen(arr2);

int len = len1 > len2 ? len1 : len2;

다음으로 이 문제의 핵심 부분이라고 볼 수 있는 덧셈 파트이다. 문자를 숫자로바꾸기 위해 각 자리수에서 ‘0’을 빼준뒤 더하는것을 기본으로 한다. 이때 두 수의 합이 10보다 크거나 같게되는 경우 다음 자리수에 1을 더해줘야 하므로 carry라는 변수를 하나 사용한다.

sum = arr1[i] - '0' + arr2[i] - '0' + carry;

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

그다음 숫자로 바뀐 해당 문자를 다시 문자로 바꿔주기 위해 ‘0’을 더해주고 res에 저장한다.

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

여기서 한가지 예외처리를 해줄것이 있는데 바로 두 문자열의 자리수가 다른경우이다. 다음 이미지를 보면 이해가 빠를 것이다.

12345 + 1234를 하는 과정인데 reverse함수 처리하면 그림의 아래 부분과 같다. 이렇게 되면 배열 4번째에서 1과 null값을 더하게 된다. 그런데 위의 sum코드에서 각 숫자마다 ‘0’을 빼줬으므로 이런경우 sum이 음수가 된다. ( null의 ASCII값 : 0 , ‘0’의 ASCII값 : 48 )

‘1’ - ‘0’ + null - ‘0’
// 49 - 48 + 0 - 48로 음수가 된다.

따라서 sum이 음수일 경우 ‘0’을 더해주는 예외처리를 해준다.

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

한가지 예외처리가 또있다. 가장 큰 자리수의 합이 10이 넘을 경우 배열의 마지막에 1을 추가해줘야만 한다.

if (carry == 1) res[len] = '1';

풀이

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

void reverse(char*, int);

void reverse(char *arr, int len) {
	char temp;

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

int main() {
	char arr1[10002] = { 0 }, arr2[10002] = { 0 }, res[10002] = { 0 };
	int sum = 0, carry = 0;

	scanf("%s %s", arr1, arr2);

	int len1 = strlen(arr1);
	int len2 = strlen(arr2);

	int len = len1 > len2 ? len1 : len2;

	reverse(arr1, len1);
	reverse(arr2, len2);

	for (int i = 0; i < len; i++) {
		sum = arr1[i] - '0' + arr2[i] - '0' + carry;

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

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

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

	if (carry == 1) res[len] = '1';

	reverse(res, strlen(res));

	printf("%s\n", res);

	return 0;
}