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의 10n과 NOT_COUNT의 n의 숫자를 같이 변경해도 답이 잘 나온다. (n < 18)
'알고리즘 > [EXP] 삼성 SW 역량 테스트 C형' 카테고리의 다른 글
더블 링크드 리스트 구현 (Double Linked List Tail ver) (0) | 2023.07.30 |
---|---|
더블 링크드 리스트 구현 (Double Linked List) (0) | 2023.07.30 |
BOJ 15688 : 수 정렬하기 5 with In-Place Sort (0) | 2023.07.29 |
중위 표기식 직접 연산하기 (0) | 2023.07.29 |
괄호가 있는 중위 표기식 연산하기 (0) | 2023.07.29 |
댓글