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

백준 온라인 저지(BOJ) 10757번 큰 수 A+B

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

10757번: 큰 수 A+B

* 사용언어 : C언어, C++

 

1. 문제

최대 10^10000 크기의 두 정수 A 와 B 의 합을 출력

 

2. 풀이

int 는 2^32(대략 -21억 ~ 21억)까지 저장 가능하므로 10진수 9자리까지 저장 가능합니다.

long long int 를 쓰더라도 2^64 까지 이므로 최대 18자리까지 저장할 수 있습니다.

그렇기 때문에 변수 1개로는 10000자리 정수를 저장하고 연산할 수 없습니다.

 

이와 같이 큰 자리 정수를 연산하기 위해서는

배열을 사용하여 정수를 나누어 저장한 뒤 계산해야 합니다.

 

더하기 연산은 입력받은 문자 A, B 를 거꾸로 보면서 더해주면 되고,

이 때 더한 값이 10보다 크면 1을 다음 자리로 넘겨주면 됩니다.

 

역순 처리와 올림 처리를 편하게 하기 위해서 문자별 index 를 따로 두었고

A 와 B 는 뒤에서 앞으로, S(sum) 은 앞에서 뒤로 저장했습니다.

 

그 밖의 설명은 생략하고 아래 코드로 설명을 대체하겠습니다.

 

 

추가로 각 배열의 공간을 1자리만 사용하지 않고 최대한 큰 숫자를 저장하면서

올림 처리를 최소로 하도록 구현하는 방식이 있습니다.

이 문제 풀이에서는 그 내용을 생략했는데, 관심이 있으면 아래 링크 참고하시면 됩니다.

 

https://rightbellboy.tistory.com/145

[정올/JUNGOL] 1374번 긴 자리 덧셈 뺄셈 (C/C++)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10757_큰 수 A+B
1140kb	0ms
*/
#include <cstdio>

const int LM = 10000;
char a[LM], b[LM], sum[LM + 1];

int my_strlen(const char *s) {
	int len = 0;
	while (*s++) len++;
	return len;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%s %s", a, b);
	
	int aIdx = my_strlen(a) - 1;
	int bIdx = my_strlen(b) - 1;
	int sIdx = 0;

	while (aIdx >= 0 || bIdx >= 0) {
		if (aIdx >= 0) sum[sIdx] += a[aIdx--] - '0';
		if (bIdx >= 0) sum[sIdx] += b[bIdx--] - '0';

		if (sum[sIdx] > 9) {
			sum[sIdx] %= 10;
			sum[sIdx + 1] = 1;
		}
		++sIdx;
	}
	sIdx += (sum[sIdx]);

	for (int i = sIdx - 1; i >= 0; --i) printf("%d", sum[i]);
	return 0;
}