BOJ 10757 : 큰 수 A+B

알고리즘 문제 전체 링크

삼성 C형 전체 링크

 

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

 

참고 

- BOJ 10757 : 큰 수 A+B
- BOJ 10757 : 큰 수 A+B with 10^N진법
- BOJ 2338 : 긴자리 계산
- BOJ 2338 : 긴자리 계산 with 10^N진법
- 36진법 긴자리 두 수의 곱셈
- 36진법 긴자리 두 수의 곱셈 with 36^5진법
- 36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input

 

 

큰 수의 덧셈은 3가지 방법으로 가능하다.

 

1. 더 짧은 자리 앞에 긴 자리 수 만큼 '0'을 추가하고 더하기

2. 문자열을 뒤집고 계산한 후, 다시 뒤집기

3. int로 변경한 후, 뒤집고, 다시 뒤집은 후, char로 변경하기

 

참고로 위의 경우는 모든 수가 양의 정수로 들어온다.

---

더 짧은 자리 앞에 긴 자리 수 만큼 '0'을 추가하고 더하기

 

두 정수 A와 B의 자릿수를 비교해서 더 큰 수를 A로 변경한다.

int lenA, lenB, diff;
for (lenA = 0; a[lenA] != 0; lenA++);
for (lenB = 0; b[lenB] != 0; lenB++);

if (lenA < lenB) // a를 더 큰 수로 변경.
{
	char* ctmp = a;
	a = b;
	b = ctmp;

	int tmp = lenA;
	lenA = lenB;
	lenB = tmp;
}

 

두 수의 길이의 차 diff 만큼 더 작은 숫자 B를 뒤로 민다.

그리고 앞의 남은 칸에 '0' 을 채운다.

diff = lenA - lenB;
for (int i = lenB; i >= 0; i--) b[i + diff] = b[i];
for (int i = 0; i < diff; i++) b[i] = '0';

 

result에 두 값을 더한다. 

이때 문자열 '0' 만큼 더해지므로 '0'을 빼야 한다.

그리고 '9' 보다 큰 값은 자리 올림을 한다.

for (int i = lenA - 1; i >= 1; i--)
{
	result[i] += (a[i] + b[i] - '0');
	if (result[i] > '9')
	{
		result[i] -= 10;
		result[i - 1] = 1;
	}
}

result[0] += (a[0] + b[0] - '0');

 

마지막 앞자리에 대해서는 따로 처리한다.

마지막 앞자리가 '9'보다 크다는 것은 자릿수가 올라야 하므로 길이가 길어진다.

따라서 한 칸 뒤로 답을 미루고 '1'을 추가한다.

	if (result[0] > '9')
	{
		for (int i = lenA; i >= 0; i--) result[i + 1] = result[i];

		result[1] -= 10;
		result[0] = '1';
		lenA++;
	}

	result[lenA] = 0;

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10010)

char A[MAX];
char B[MAX];
char result[MAX];

void bigPlus(char a[MAX], char b[MAX], char result[MAX])
{
	int lenA, lenB, diff;
	for (lenA = 0; a[lenA] != 0; lenA++);
	for (lenB = 0; b[lenB] != 0; lenB++);

	if (lenA < lenB) // a를 더 큰 수로 변경.
	{
		char* ctmp = a;
		a = b;
		b = ctmp;

		int tmp = lenA;
		lenA = lenB;
		lenB = tmp;
	}

	diff = lenA - lenB;
	for (int i = lenB; i >= 0; i--) b[i + diff] = b[i];
	for (int i = 0; i < diff; i++) b[i] = '0';

	for (int i = lenA - 1; i >= 1; i--)
	{
		result[i] += (a[i] + b[i] - '0');
		if (result[i] > '9')
		{
			result[i] -= 10;
			result[i - 1] = 1;
		}
	}

	result[0] += (a[0] + b[0] - '0');

	if (result[0] > '9')
	{
		for (int i = lenA; i >= 0; i--) result[i + 1] = result[i];

		result[1] -= 10;
		result[0] = '1';
		lenA++;
	}

	result[lenA] = 0;
}

int main()
{
	scanf("%s %s", A, B);

	bigPlus(A, B, result);

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

	return 0;
}

---

문자열을 뒤집고 계산한 후, 다시 뒤집기

 

위의 방법은 '0'을 채우기 위해 숫자를 미루고 마지막 자릿 수 올림을 처리하기 귀찮다는 단점이 있다.

그래서 처음부터 문자열을 뒤집은 다음, 계산이 끝나면 다시 뒤집는 방법을 이용할 수 있다.

 

뒤집을 문자열 ra, rb에 A와 B를 뒤집어서 저장하고, 둘 중 더 길이가 큰 경우에 맞춰서 뒤에 '0'을 채운다.

char ra[MAX] = { 0 }; // reverse
char rb[MAX] = { 0 };
char temp[MAX] = { 0 };

int lenA, lenB;
for (lenA = 0; a[lenA] != 0; lenA++);
for (lenB = 0; b[lenB] != 0; lenB++);

for (int i = 0; i < lenA; i++) ra[lenA - 1 - i] = a[i];
for (int i = 0; i < lenB; i++) rb[lenB - 1 - i] = b[i];

int len = (lenA > lenB) ? lenA : lenB;

for (int i = lenA; i < len; i++) ra[i] = '0';
for (int i = lenB; i < len; i++) rb[i] = '0';

 

temp에 연산 결과를 저장하고, 마지막에 뒤집는다.

	for (int i = 0; i < len; i++)
	{
		temp[i] += (ra[i] + rb[i] - '0');
		if (temp[i] > '9')
		{
			temp[i] -= 10;
			temp[i + 1] = 1;
		}
	}

	if (temp[len] == 1) // 자릿수가 올라가는 경우 문자로 전환
	{
		temp[len] = '1';
		len++;
	}

	for (int i = 0; i < len; i++) result[len - 1 - i] = temp[i];

	result[len] = 0;

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10010)

char A[MAX];
char B[MAX];
char result[MAX];

void bigPlus(char a[MAX], char b[MAX], char result[MAX])
{
	char ra[MAX] = { 0 }; // reverse
	char rb[MAX] = { 0 };
	char temp[MAX] = { 0 };

	int lenA, lenB;
	for (lenA = 0; a[lenA] != 0; lenA++);
	for (lenB = 0; b[lenB] != 0; lenB++);

	for (int i = 0; i < lenA; i++) ra[lenA - 1 - i] = a[i];
	for (int i = 0; i < lenB; i++) rb[lenB - 1 - i] = b[i];

	int len = (lenA > lenB) ? lenA : lenB;

	for (int i = lenA; i < len; i++) ra[i] = '0';
	for (int i = lenB; i < len; i++) rb[i] = '0';

	for (int i = 0; i < len; i++)
	{
		temp[i] += (ra[i] + rb[i] - '0');
		if (temp[i] > '9')
		{
			temp[i] -= 10;
			temp[i + 1] = 1;
		}
	}

	if (temp[len] == 1) // 자릿수가 올라가는 경우 문자로 전환
	{
		temp[len] = '1';
		len++;
	}

	for (int i = 0; i < len; i++) result[len - 1 - i] = temp[i];

	result[len] = 0;
}


int main()
{
	scanf("%s %s", A, B);

	bigPlus(A, B, result);

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

	return 0;
}

---

int로 변경한 후, 뒤집고, 다시 뒤집은 후, char로 변경하기

 

매번 '0' 연산을 고려하는 것 보다는 int 배열로 받은 후, char로 변경하는 방법이 더 나을 수 있다.

 

먼저 다음과 같은 구조체를 정의하자.

num은 int로 저장되는 자릿수이고 len은 숫자의 길이이다.

typedef struct st
{
	int num[MAX];
	int len;
}BIG_NUMBER;

 

BIG_NUMBER에는 숫자를 거꾸로 저장한다.

따라서 문자열로 받은 긴 자리 수를 아래와 같이 거꾸로 저장하고 길이도 저장한다.

void makeNumber(BIG_NUMBER& big, char number[MAX])
{
	int len;
	for (len = 0; number[len]; len++);

	for (int i = 0; i < len; i++) big.num[len - 1 - i] = number[i] - '0';

	big.len = len;
}

 

나중에 결과를 출력할 때는 반대로 문자열로 전환해야 하므로 아래의 함수도 만들어둔다.

void changeIntToChar(BIG_NUMBER& big, char answer[MAX])
{
	int len = big.len;
	for (int i = 0; i < len; i++) answer[len - 1 - i] = big.num[i] + '0';

	answer[len] = 0;
}

 

덧셈은 단순히 각 길이에 있는 수만큼 temp에 누적하면 된다. 

초기화할 때 이미 0이므로 '0'을 채우지 않아도 되는 장점이 있다.

BIG_NUMBER bigPlus(BIG_NUMBER& a, BIG_NUMBER& b)
{
	BIG_NUMBER result = { 0 };
	int lenA, lenB, len;
	int temp[MAX] = { 0 };

	lenA = a.len;
	lenB = b.len;
	len = (lenA > lenB) ? lenA : lenB;

	for (int i = 0; i < lenA; i++) temp[i] += a.num[i];
	for (int i = 0; i < lenB; i++) temp[i] += b.num[i];

	for (int i = 0; i < len; i++)
	{
		temp[i + 1] += (temp[i] / 10);
		temp[i] %= 10;
	}

	len++; // 자릿수가 오른 경우 체크
	while (len && temp[len] == 0) len--;
	len++;

	for (int i = 0; i < len; i++) result.num[i] = temp[i];

	result.len = len;

	return result;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10010)

typedef struct st
{
	int num[MAX];
	int len;
}BIG_NUMBER;

char A[MAX];
char B[MAX];
char ANSWER[MAX];

BIG_NUMBER bigPlus(BIG_NUMBER& a, BIG_NUMBER& b)
{
	BIG_NUMBER result = { 0 };
	int lenA, lenB, len;
	int temp[MAX] = { 0 };

	lenA = a.len;
	lenB = b.len;
	len = (lenA > lenB) ? lenA : lenB;

	for (int i = 0; i < lenA; i++) temp[i] += a.num[i];
	for (int i = 0; i < lenB; i++) temp[i] += b.num[i];

	for (int i = 0; i < len; i++)
	{
		temp[i + 1] += (temp[i] / 10);
		temp[i] %= 10;
	}

	len++; // 자릿수가 오른 경우 체크
	while (len && temp[len] == 0) len--;
	len++;

	for (int i = 0; i < len; i++) result.num[i] = temp[i];

	result.len = len;

	return result;
}

void makeNumber(BIG_NUMBER& big, char number[MAX])
{
	int len;
	for (len = 0; number[len]; len++);

	for (int i = 0; i < len; i++) big.num[len - 1 - i] = number[i] - '0';

	big.len = len;
}

void changeIntToChar(BIG_NUMBER& big, char answer[MAX])
{
	int len = big.len;
	for (int i = 0; i < len; i++) answer[len - 1 - i] = big.num[i] + '0';

	answer[len] = 0;
}

int main()
{
	scanf("%s %s", A, B);

	BIG_NUMBER a, b, result;

	makeNumber(a, A);
	makeNumber(b, B);

	result = bigPlus(a, b);

	changeIntToChar(result, ANSWER);

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

	return 0;
}

---

이 방법도 char로 다시 변환하는 과정이 있어 크게 이득이 없는 것 같지만,

10진법 이상 연산을 응용할 수 있어 빠르게 덧셈을 할 수 있다.