본문 바로가기
알고리즘/BAEKJOON

BOJ 2338 : 긴자리 계산

by 피로물든딸기 2023. 7. 29.
반응형

알고리즘 문제 전체 링크

삼성 C형 전체 링크

 

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

 

참고

- 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의 덧셈, 뺄셈, 곱셈을 해보자.

10진수로 1,000자리가 주어지며, 곱셈 연산에 의해 최대 자릿수는 2,000이다.

큰 수의 정의

 

큰 수를 정의하기 위해 char 배열, 문자열의 길이, 그리고 부호를 가지는 구조체를 선언한다.

자릿수가 최대 1000이기 때문에 MAX를 2000으로 잡았다. 

#define MAX (2010)

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

 

덧셈, 뺄셈, 곱셈을 구현해야 하는데, 이 문제는 부호가 있기 때문에 매우 까다롭다.

예를 들어 A - (-B)는 사실 A + B가 된다.

따라서 부호 처리는 나중에 하고,

각 함수는 부호를 모두 + 로 가정하고, 덧셈 함수는 덧셈만, 뺄셈 함수는 뺄셈만 한다.

 

이때, 뺄셈의 경우 문제가 발생한다. 

A - B에서 B가 큰 경우 부호가 - 가 된다.

따라서 둘 중 누가 더 큰지 비교하는 함수를 하나 더 만들어, 반드시 큰 값에서 작은 값을 빼도록 한다.

 

따라서 구현해야 할 함수는 다음과 같다.

 

1. isBig : A > B라면 true

2. bigPlus : 같은 부호를 더하는 연산

3. bigMinus : 더 큰 수에서 작은 수를 빼는 연산

4. bigMultiply : 같은 부호를 곱하는 연산

isBig 

 

BIG_NUMBER 구조체를 정의하였으므로, isBig은 다음과 같다.

문자열 길이가 더 큰 쪽이 값이 더 크고, 같은 문자열의 길이라면 하나씩 비교한다.

bool isBig(BIG_NUMBER& a, BIG_NUMBER& b)
{
	if (a.len != b.len) return a.len > b.len;

	for (int i = a.len - 1; i >= 0; i--)
	{
		if (a.num[i] != b.num[i]) return a.num[i] > b.num[i];
	}

	return true;
}

bigPlus 

 

큰 수 A+B를 참고하자.

int로 변경한 후, 뒤집고, 다시 뒤집은 후, char로 변경하는 방법을 사용하므로 아래와 같이 구현하였다.

이 방법은 N진법 연산을 사용할 때 편하다.

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;
}

bigMinus

 

bigMinus는 큰 수에서 작은 수를 빼기 때문에 덧셈과 구현내용이 거의 비슷하다.

temp에 A를 더하고 B는 뺀다.

BIG_NUMBER bigMinus(BIG_NUMBER& a, BIG_NUMBER& b)
{
	BIG_NUMBER result = { 0 };
	int lenA, lenB, len;
	char 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++)
	{
		if (temp[i] < 0)
		{
			temp[i] += 10;
			temp[i + 1]--;
		}
	}

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

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

	result.len = len;

	return result;
}

bigMultiply

 

A에서 i 번째 수와 B에서 k 번째 수를 곱하면 i + k 번째 자릿수에 덧셈을 하는 것이 곱셈이다.

이중 for문을 돌면서 곱셈을 끝내고 덧셈처럼 자릿수 올림을 처리하면 된다.

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

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

	len = lenA + lenB + 1;

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

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

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

	return result;
}

문자열 변환과 출력

 

문자열을 BIG_NUMBER로 변환하는 함수와 BIG_NUMBER를 문자열로 변환하는 함수,

그리고 음의 부호가 있는 경우 출력하기 위한 showResult 함수는 다음과 같다.

-0이 출력되지 않도록 len = 1이고 num[0] == 0인 경우는 부호를 +로 바꾼다.

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;
}

void showResult(BIG_NUMBER& result)
{
	char answer[MAX] = { 0 };

	if (result.len == 1 && result.num[0] == 0) result.sign = 1;

	changeIntToChar(result, answer);
	
	if (result.sign == -1) printf("-");
	printf("%s\n", answer);
}

연산

 

이제 위의 함수를 이용해서 긴 자리 계산을 해보자.

 

A와 B의 부호가 +, + / +, - / -, + / -, - 인 경우를 나눠서 덧셈, 뺄셈, 곱셈을 실행하면 된다.

 

+, + 

 

이 경우 덧셈 연산은 반드시 부호가 + 가 된다.

뺄셈인 경우 A > B라면 부호가 +, A < B라면 - 가 된다.

이렇게 경우를 나누면 덧셈과 뺄셈은 아래와 같이 경우가 나뉜다.

if (A.sign == 1 && B.sign == 1)
{
	result = bigPlus(A, B);
	result.sign = 1;
	showResult(result);

	if (isBig(A, B))
	{
		result = bigMinus(A, B);
		result.sign = 1;
	}
	else
	{
		result = bigMinus(B, A);
		result.sign = -1;
	}

	showResult(result);
}

 

+, - 

 

이 경우 덧셈은 A가 더 큰 경우 +, B가 더 큰 경우 -다.

그리고 실제로는 빼는 연산이므로 bigMinus를 이용하고 부호만 변경한다.

반대로 A와 B의 크기에 상관없이 뺄셈 연산은 사실 덧셈 연산이므로, 더하면 된다.

	else if (A.sign == 1 && B.sign == -1)
	{
		result.sign = 1;

		if (isBig(A, B))
		{
			result = bigMinus(A, B);
			result.sign = 1;
		}
		else
		{
			result = bigMinus(B, A);
			result.sign = -1;
		}

		showResult(result);

		result = bigPlus(A, B);
		result.sign = 1;
		showResult(result);
	}

 

-, + / -, - 는 전체 코드를 참고하자.

곱셈은 부호가 다른 경우 -, 같으면 +로 처리하면 된다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (2010)

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

bool isBig(BIG_NUMBER& a, BIG_NUMBER& b)
{
	if (a.len != b.len) return a.len > b.len;

	for (int i = a.len - 1; i >= 0; i--)
	{
		if (a.num[i] != b.num[i]) return a.num[i] > b.num[i];
	}

	return true;
}

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;
}

BIG_NUMBER bigMinus(BIG_NUMBER& a, BIG_NUMBER& b)
{
	BIG_NUMBER result = { 0 };
	int lenA, lenB, len;
	char 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++)
	{
		if (temp[i] < 0)
		{
			temp[i] += 10;
			temp[i + 1]--;
		}
	}

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

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

	result.len = len;

	return result;
}

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

	lenA = a.len;
	lenB = b.len;

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

	len = lenA + lenB + 1;

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

	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;
}

void showResult(BIG_NUMBER& result)
{
	char answer[MAX] = { 0 };

	if (result.len == 1 && result.num[0] == 0) result.sign = 1;

	changeIntToChar(result, answer);
	
	if (result.sign == -1) printf("-");
	printf("%s\n", answer);
}

int main()
{
	int len;
	char inputA[MAX], inputB[MAX];

	BIG_NUMBER A, B, result = { 0 };

	scanf("%s %s", inputA, inputB);

	if (inputA[0] == '-')
	{
		makeNumber(A, inputA + 1);
		A.sign = -1;
	}
	else
	{
		makeNumber(A, inputA);
		A.sign = 1;
	}

	if (inputB[0] == '-')
	{
		makeNumber(B, inputB + 1);
		B.sign = -1;
	}
	else
	{
		makeNumber(B, inputB);
		B.sign = 1;
	}

	/* ------------------------------------------------------------------------- */

	if (A.sign == 1 && B.sign == 1)
	{
		result = bigPlus(A, B);
		result.sign = 1;

		showResult(result);

		if (isBig(A, B))
		{
			result = bigMinus(A, B);
			result.sign = 1;
		}
		else
		{
			result = bigMinus(B, A);
			result.sign = -1;
		}

		showResult(result);
	}
	else if (A.sign == 1 && B.sign == -1)
	{
		result.sign = 1;

		if (isBig(A, B))
		{
			result = bigMinus(A, B);
			result.sign = 1;
		}
		else
		{
			result = bigMinus(B, A);
			result.sign = -1;
		}

		showResult(result);

		result = bigPlus(A, B);
		result.sign = 1;

		showResult(result);
	}
	else if (A.sign == -1 && B.sign == 1)
	{
		if (isBig(B, A))
		{
			result = bigMinus(B, A);
			result.sign = 1;
		}
		else
		{
			result = bigMinus(A, B);
			result.sign = -1;
		}

		showResult(result);

		result = bigPlus(A, B);
		result.sign = -1;

		showResult(result);
	}
	else // if (A.sign == -1 && B.sign == -1)
	{
		result = bigPlus(A, B);
		result.sign = -1;

		showResult(result);

		if (isBig(A, B))
		{
			result = bigMinus(A, B);
			result.sign = -1;
		}
		else
		{
			result = bigMinus(B, A);
			result.sign = 1;
		}

		showResult(result);
	}

	result = bigMultiply(A, B);
	result.sign = A.sign * B.sign;

	showResult(result);

	return 0;
}
반응형

'알고리즘 > BAEKJOON' 카테고리의 다른 글

BOJ 12015 : 가장 긴 증가하는 부분 수열 2  (1) 2024.12.20
BOJ 10757 : 큰 수 A+B  (0) 2023.07.29
BOJ 7453 : 합이 0인 네 정수  (0) 2023.04.07
BOJ 1991 : 트리 순회  (0) 2023.04.07
BOJ 6593 : 상범 빌딩  (0) 2023.03.26

관련글

댓글

티스토리툴바