반응형
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 with N진법을 참고하여 뺄셈과 곱셈도 마찬가지로 N진법을 적용해보자.
덧셈의 경우 100000000000000000진법까지 가능했지만,
곱셈은 자릿수가 2배로 오르기 때문에 100000000진법(0이 8개)까지만 가능하다.
#include <stdio.h>
typedef long long int ll;
int main()
{
ll a = 1000000000; // 0의 개수 9
ll b = a * a;
printf("%lld\n", b);
printf("%lld\n", 9223372036854775807);
return 0;
}
10000000000 x 1000000000 (0이 9개) = 1000000000000000000이지만
99999999999 x 9999999999 는 9223372036854775807를 초과하기 때문에
0이 8개인 100000000진법이 최대다.
또한 이 문제의 경우 1,000자리 수 곱이기 때문에 100,000,000진법으로 통과하지만,
자릿수가 높아질수록 아래의 식에서 덧셈에 의해 overflow가 발생할 수 있다.
for (int i = 0; i < lenA; i++)
for (int k = 0; k < lenB; k++)
temp[i + k] += (a.num[i] * b.num[k]);
이 경우도 고려해야하므로, 몇 진법까지 괜찮은지는 스스로 찾아갈 수 밖에 없다.
typedef를 이용하여 long long int를 ll로 정의한다.
그리고 NOTATION = 100000000진법, 그리고 NOT_COUNT는 자릿수의 0의 개수로 정의한다.
이전에 정의한 구조체 BIG_NUMBER의 배열의 크기는 줄일 수 있지만,
여기서는 메모리가 부족하지 않으므로 그대로 MAX를 사용하였다.
typedef long long int ll;
#define NOTATION (100000000)
#define NOT_COUNT (8) // 10진법 = 1, 100진법 = 2, 1000진법 = 3 ... 100000000진법 = 8
typedef struct st
{
ll num[MAX]; // <- // long 연산 때문에 MAX 보다 작은 값을 사용해도 된다.
int len;
int sign;
}BIG_NUMBER;
BIG_NUMBER의 num 타입이 변경되었으므로 bigPlus, bigMinus, bigMultiply의 temp도 type을 ll로 바꾼다.
BIG_NUMBER bigPlus(BIG_NUMBER& a, BIG_NUMBER& b)
{
BIG_NUMBER result = { 0 };
int lenA, lenB, len;
ll temp[MAX] = { 0 };
...
이후 설명은 큰 수 A+B with 10^N진법와 동일하므로, 전체 코드를 참고하자.
#include <stdio.h>
#define MAX (2010)
typedef long long int ll;
#define NOTATION (100000000)
#define NOT_COUNT (8) // 10진법 = 1, 100진법 = 2, 1000진법 = 3 ... 100000000진법 = 8
typedef struct st
{
ll 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;
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;
}
BIG_NUMBER bigMinus(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++)
{
if (temp[i] < 0)
{
temp[i] += NOTATION;
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;
ll 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] / NOTATION);
temp[i] %= NOTATION;
}
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;
}
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;
}
NOTATION의 10n과 NOT_COUNT의 n의 숫자를 같이 변경해도 답이 잘 나온다. (n < 9)
반응형
'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글
| 36진법 긴자리 두 수의 곱셈 with 36^5진법 (0) | 2023.08.26 |
|---|---|
| 36진법 긴자리 두 수의 곱셈 (0) | 2023.08.26 |
| 긴자리 후위 표기법 구현하기 (0) | 2023.08.25 |
| BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 (0) | 2023.08.25 |
| 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 (1) | 2023.08.25 |
댓글