[백준/C++] 10757번 : 큰 수 A+B - unsigned long long을 넘는 자료형의 덧셈(string)

큰 수 A+B 

문제

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

입력

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

출력

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

예제 입력 1 

9223372036854775807 9223372036854775808

예제 출력 1 

18446744073709551615

---

해당 문제는 unsigned long long 자료형의 범위를 훨씬 뛰어넘는 큰 숫자들의 덧셈을 구현하는 문제이다.

 

그어떤 정수형 자료형으로도 범위를 나타낼 수 없으므로 string으로 숫자를 입력받은 뒤 각 자릿수의 덧셈을 순정으로 구현해주어야 이 문제를 해결할 수 있다. (너무 어려웠다..)

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main()
{
	vector<int> result;
	string A, B;
	
	cin >> A >> B;

	// A를 (자릿수가)더 큰수로 변경
	if(A.length() < B.length())
	{
		string temp = A;
		A = B;
		B = temp;
	}

	vector<int> aNum(A.length());
	vector<int> bNum(A.length());

	for(int i = 0; i < aNum.size(); i++)
	{
		aNum[i] = A[i] - '0';
		if (i < B.size())
			bNum[A.size()-B.size()+i] = B[i] - '0';
	}

	//cout << "A : " << A << endl;
	//cout << "B : " << B<< endl;

	for(int i = aNum.size()-1; i >= 0; i--)
	{
		int sum = aNum[i] + bNum[i];
		if (sum >= 10)
		{
			sum -= 10;
			if (i - 1 < 0)
			{
				result.push_back(sum);
				result.push_back(1);
				break;
			}
			aNum[i - 1]++;
		}
		result.push_back(sum);
	}

	reverse(result.begin(), result.end());

	for (int num : result)
		cout << num;
	cout << endl;

	return 0;
}

 

1. 숫자 A와 B를 각각 string 자료형에 저장하였다.

2. 자릿수가 더 큰 숫자가 무조건 A 변수에 위치하도록 하였다.

3. 더 큰 수인 A의 길이만큼 vector<int>를 각각 생성하여 A와 B의 각 자릿수를 int형으로 저장해두었다.

이때, B의 자릿수가 부족하다면 빈 자리에는 0을 채워두도록 자릿수를 맞춰서 인덱스를 추가하였다.

4. 두 수의 끝자리부터 더한 후 합이 10을 넘어가는 경우 앞자릿수에 1을 더하고 10을 뺀 뒷자릿수는 Result 배열에 Push_Back 하였다.

5. 모든 자릿수의 연산이 끝난 후 Result 배열에는 숫자들이 거꾸로 배치되어있기 때문에 Reverse를 이용해 뒤집어준 뒤 출력하였다.