BOJ 10757 : 큰 수 A+B with 10^N진법

알고리즘 문제 전체 링크

삼성 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

 

 

큰 수 A+B에서 아래의 방법으로 큰 수를 계산했었다.

 

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

 

이 방법을 확장하면 더 빠르게 연산이 가능하다.

 

매번 배열을 한 칸씩 계산하는 것 보다 배열 한 개에 최대한 많은 숫자를 넣은 후, 한꺼번에 더한다.

예를 들어 1234567890 + 1234567890 을 더한다면,

 

12345 + 12345 = 24690

67890 + 67890 = 135780

 

-> 자리 올림으로 인해 24690에 1을 더하고 135780에서는 1을 빼서 35780이 된다.

그리고 다시 2469135780으로 합친다.

---

구현

 

아래의 코드를 실행해보자.

#include <stdio.h>

typedef long long int ll;

int main()
{
	ll a = 1000000000000000000; // 0의 개수 18
	ll b = a + a;
    
	printf("%lld\n", b);
	printf("%lld\n", 9223372036854775807);
    
	return 0; 
}

 

long int의 최대 값은 9223372036854775807 다.

따라서 100000000000000000 → 0이 17개, 즉 18자리 수 연산까지는 long int로 덧셈이 가능하다.

18자리 수를 더해서 19자리 수가 넘어가면 overflow가 발생한다.

 

typedef를 이용하여 long long int를 ll로 정의한다.

그리고 NOTATION = 100000000000000000진법, 그리고 NOT_COUNT는 자릿수의 0의 개수로 정의한다.

이전에 정의한 구조체 BIG_NUMBER의 배열의 크기는 줄일 수 있지만,

여기서는 메모리가 부족하지 않으므로 그대로 MAX를 사용하였다.

typedef long long int ll;

#define NOTATION (100000000000000000)
#define NOT_COUNT (17) // ↑ 0의 개수

typedef struct st
{
	ll num[MAX]; // <-  // long 연산 때문에 MAX 보다 작은 값을 사용해도 된다.
	int len;
}BIG_NUMBER;

 

BIG_NUMBER의 num 타입이 변경되었으므로 bigPlus의 temp도 type을 ll로 바꾼다.

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

 

문자열 number를 NOTATION 진법으로 만든다.

예를 들어 10진법이라면 num 한 칸에 0 ~ 9가 들어가고, 100진법이라면 0 ~ 99가 들어간다.

마찬가지로 이 값은 유지하되, 거꾸로 넣어야 나중에 연산하기 편하다.

(123456을 100진법으로 나타내면 56 / 34 / 12 로 저장된다.)

void makeNumber(BIG_NUMBER& big, char number[MAX])
{
	char reverse[MAX] = { 0 };
	int len, nLen;

	for (len = 0; number[len]; len++);

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

	nLen = 0;
	for (int i = 0; i < len; i += NOT_COUNT)
	{
		ll tmp = 0;
		for (int k = i + NOT_COUNT - 1; k >= i; k--) tmp = tmp * 10 + reverse[k];

		big.num[nLen++] = tmp;
	}

	big.len = nLen;
}

 

연산이 끝났으면 다시 문자열로 바꿔야 한다.

temp에 한 자리씩 저장한 다음 문자열을 거꾸로 바꾼다.

void changeIntToChar(BIG_NUMBER& big, char answer[MAX])
{
	char temp[MAX] = { 0 };

	int len = big.len;

	int count = 0;
	for (int i = 0; i < len; i++)
	{
		for (int k = 0; k < NOT_COUNT; k++)
		{
			temp[count++] = (big.num[i] % 10);
			big.num[i] /= 10;
		}
	}

	while (count && temp[count] == 0) count--;
	count++;

	temp[count] = 0;

	int half = count / 2;
	for (int i = 0; i < half; i++)
	{
		char tmp = temp[i];
		temp[i] = temp[count - 1 - i];
		temp[count - 1 - i] = tmp;
	}

	for (int i = 0; i < count; i++) answer[i] = temp[i] + '0';

	answer[count] = 0;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (10010)

typedef long long int ll;

#define NOTATION (100000000000000000)
#define NOT_COUNT (17) // ↑ 0의 개수

typedef struct st
{
	ll num[MAX]; // <-  // long 연산 때문에 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;
	ll 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] / NOTATION);
		temp[i] %= NOTATION;
	}

	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])
{
	char reverse[MAX] = { 0 };
	int len, nLen;

	for (len = 0; number[len]; len++);

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

	nLen = 0;
	for (int i = 0; i < len; i += NOT_COUNT)
	{
		ll tmp = 0;
		for (int k = i + NOT_COUNT - 1; k >= i; k--) tmp = tmp * 10 + reverse[k];

		big.num[nLen++] = tmp;
	}

	big.len = nLen;
}

void changeIntToChar(BIG_NUMBER& big, char answer[MAX])
{
	char temp[MAX] = { 0 };

	int len = big.len;

	int count = 0;
	for (int i = 0; i < len; i++)
	{
		for (int k = 0; k < NOT_COUNT; k++)
		{
			temp[count++] = (big.num[i] % 10);
			big.num[i] /= 10;
		}
	}

	while (count && temp[count] == 0) count--;
	count++;

	temp[count] = 0;

	int half = count / 2;
	for (int i = 0; i < half; i++)
	{
		char tmp = temp[i];
		temp[i] = temp[count - 1 - i];
		temp[count - 1 - i] = tmp;
	}

	for (int i = 0; i < count; i++) answer[i] = temp[i] + '0';

	answer[count] = 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;
}

 

NOTATION의 10ⁿ과 NOT_COUNT의 n의 숫자를 같이 변경해도 답이 잘 나온다.  (n < 18)