[C++] 백준 10757 - 큰 수 A+B(문자열 덧셈, strlen)

 

0. [c++] 백준  - 10757

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

1. 풀이

1) 10^10000의 수를 처리하기 위해서는 기본적인 int를 활용하면 안된다. 기본적인 int는 32자리를 처리하므로 평소에 활용하는 string을 활용하고자 접근했다.

하지만, string으로도 입력을 처리하지 못하여서 char를 활용하는 방법을 선택하였다.

 

입력받을 char를 배열로 미리 만들어주었다. (추가적으로 이를 선택한 이유는 int보다 더 적은 저장공간을 할당하기 때문이다.)

 

2) 이제 입력받은 배열을 더해주는 방법을 구현해야한다. 우리가 숫자를 더할 때 1의 자리부터 서서히 올라가는 방법을 구현하기 위해서 문자열을 뒤집어주었다.

 

3) 뒤집은 문자열을 가장 앞부터 더하는 것으로 구현 완료!

 

+) 올림이 발생하는 경우, 더 큰 수에 올림을 더해주었다.

+) 더 큰 수를 무조건 A로 변경하려 고민하다 데이터 공간을 더 할당하는 문제가 발생하므로 이 방법을 선택하지 않았다.

+) if문을 많이 활용하는 코드가 되어버렸는데, for문에 들어가기 전 미리 if문을 해결해버린다면 이와 같은 문제는 발생하지 않을것이다. 코드를 수정하고 싶을때 고민해보면 좋을 것이라 생각한다.

 

+) 문제를 풀이하던 중 반례로 www.acmicpc.net/board/view/62515를 참고하며 많은 도움을 받을 수 있었다.

2. 소스코드

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

char ret[10005];
char A[10001];
char B[10001];
char temp[10001];

void reverseChar(char* str)
{
	for (int i = 0; i < strlen(str) / 2; i++)
	{
		char temp = str[i];
		str[i] = str[strlen(str) - i - 1];
		str[strlen(str) - i - 1] = temp;
	}
}


void add(char* A, char* B) {	
	reverseChar(A);
	reverseChar(B);

	for (int i = 0; (i < strlen(A))|(i<strlen(B)); i++) {
		int temp_a = A[i] - '0';
		int temp_b = B[i] - '0';
		if (temp_a < 0) temp_a = 0;
		if (temp_b < 0) temp_b = 0;
		int sum = temp_a + temp_b;
		/*cout << "[" << i << "] : " << temp_a << "   "<< temp_b << "   " << sum << endl;*/

		if (sum > 9) {
			if (strlen(B) > strlen(A)) {
				if (i == strlen(B) - 1) {
					ret[i + 1] = '1';
				}
				else {
					B[i + 1]++;
				}
			}
			else {
				if (i == strlen(A) - 1) {
					ret[i + 1] = '1';
				}
				else {
					A[i + 1]++;
				}
			}
		}

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

	reverseChar(ret);
}

int main() {
	cin >> A >> B;


	add(A, B);

	cout << ret << endl;
}​

3. 참고

 

 

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!