[C++] 큰 수 A + B : 10757번

문제

 

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

---

 

예제 입력

9223372036854775807 9223372036854775808

 

예제 출력

18446744073709551615

---

문제 풀이

 

매우 큰 두 수의 합을 출력해야 하므로 일반적인 방법으로는 계산할 수 없을 것이다.

따라서, 숫자를 문자열로 입력받아 각 자리 수마다 직접 더해서 올림하는 연산을 구현해야 한다.

이 때, 출력은 한 글자씩 출력해도, 전체를 출력해도 정답처리 된다.

또, 숫자의 입력은 01 + 2 와 같은 형식으로도 입력이 가능하지만

출력은 맨 앞 자리의 0을 생략해야 한다.

 

#include <iostream>
using namespace std;

int main()
{
	string a, b; // 입력받는 두 수
	int* A; int* B; // 두 수의 한자리 씩 담을 배열
	int* C; // 정답 배열
	cin >> a >> b;

	if (a.length() < b.length()) // 문자열이 더 긴쪽을 a 로 옮김
	{
		string temp = a;
		a = b;
		b = temp;
	}
	// 공간 할당
	A = new int[a.length()];
	B = new int[a.length()]; // a 와 자릿수를 맞춰서 공간할당
	C = new int[a.length() + 1]; // 합의 자릿수는 긴 자릿수 + 1
	// A ~ C 초기화
	for (int i = 0; i < a.length(); i++)
	{
		A[i] = 0;
		B[i] = 0;
		C[i] = 0;
	}
	C[a.length()] = 0; // C 마지막 자리 초기화

	for (int i = 0; i < a.length(); i++) // 각 자리수 저장
	{
		A[i] = a[i] - '0';
	}
	
	for (int i = 0; i < b.length(); i++) // b 가 자리수가 더 적을 수 있기에
	{	// a 길이 - b길이 만큼을 더한 위치에서부터 저장
		B[i + (a.length() - b.length())] = b[i] - '0';
	}

	for (int i = a.length() - 1; i >= 0; i--) // A, B 의 거꾸로 부터
	{
		if (A[i] + B[i] + C[i + 1] >= 10) // 자릿수 합이 두자리가 되면
		{
			C[i + 1] += A[i] + B[i] - 10; // 한 자릿수만 저장
			C[i] += 1; // 그 앞자리를 올림
		}
		else // 한자리라면
		{
			C[i + 1] += A[i] + B[i]; // 그냥 저장
		}
	}
	int start = 0; // 시작위치
	for (int i = 0; i < a.length() + 1; i++)
	{
		if (C[i] == 0) // 맨 앞글자가 0 이라면 출력하지 말아야한다
		{
			start++;
		}
		else break;
	}

	for (int i = start; i < a.length() + 1; i++) // C 의 숫자를 하나씩 출력
	{
		cout << C[i];
	}
}

 

먼저 두 수를 합해서 결과를 출력하기 위해서는 두 수의 자릿수를 맞추어야 한다.

따라서 한 쪽이 긴 쪽으로 바꿔주어야 한다.

 

if (a.length() < b.length()) // 문자열이 더 긴쪽을 a 로 옮김
	{
		string temp = a;
		a = b;
		b = temp;
	}

 

a 가 b 보다 더 긴 수라고 가정하고 a 를 기준으로 정렬하였다.

 

	// 공간 할당
	A = new int[a.length()];
	B = new int[a.length()]; // a 와 자릿수를 맞춰서 공간할당
	C = new int[a.length() + 1]; // 합의 자릿수는 긴 자릿수 + 1
	// A ~ C 초기화
	for (int i = 0; i < a.length(); i++)
	{
		A[i] = 0;
		B[i] = 0;
		C[i] = 0;
	}
	C[a.length()] = 0; // C 마지막 자리 초기화

그 후 반복문을 사용하여 각 문자의 길이만큼

다시 각 자릿수를 저장할 int 형 배열을 선언하고

초기화한다. 이 때, 결과를 저장할 C의 길이는 가장 긴 A 문자열보다 1만큼 더 길어야 모든 결과를 저장할 수 있다.

 

	for (int i = 0; i < a.length(); i++) // 각 자리수 저장
	{
		A[i] = a[i] - '0';
	}
	
	for (int i = 0; i < b.length(); i++) // b 가 자리수가 더 적을 수 있기에
	{	// a 길이 - b길이 만큼을 더한 위치에서부터 저장
		B[i + (a.length() - b.length())] = b[i] - '0';
	}

A 에는  a만큼 순서대로 아스키코드 연산을 하여 int 형으로 저장을 해준다.

B 는 A 와 연산을 하기 위해 자릿수를 맞춰야하므로, a 와 b 의 길이 차 만큼 더한 위치에서 저장을 시작한다.

 

	for (int i = a.length() - 1; i >= 0; i--) // A, B 의 거꾸로 부터
	{
		if (A[i] + B[i] + C[i + 1] >= 10) // 자릿수 합이 두자리가 되면
		{
			C[i + 1] += A[i] + B[i] - 10; // 한 자릿수만 저장
			C[i] += 1; // 그 앞자리를 올림
		}
		else // 한자리라면
		{
			C[i + 1] += A[i] + B[i]; // 그냥 저장
        }
    }

999 + 9 를 가정하고 문제를 풀면 다양한 반례가 해결될 것이다.