[정올/JUNGOL] 1262번 긴 자리 곱셈 (C/C++)

 정보 올림피아드 알고리즘 1262번 긴 자리 곱셈

https://www.jungol.co.kr/problem/1262

JUNGOL

* 사용언어 : C언어, C++

 

1. 문제

두 개의 100자리 이하의 정수를 입력받아서 두 수의 곱을 출력

 

2. 풀이

정올의 긴 자리 덧셈 뺄셈을 먼저 푼 다음에 풀어본 문제입니다.

https://www.jungol.co.kr/problem/1374

JUNGOL

해당 문제(덧셈, 뺄셈)를 풀어본 상태라고 가정하고 작성하겠습니다.

1) 문자열 입력 → int 배열 처리

문자로 입력받아서 숫자 배열로 변환해줍니다.
자세한 내용은 아래 링크 참고바랍니다.
 
[정올/JUNGOL] 1374번 긴 자리 덧셈 뺄셈 (C/C++) (tistory.com)

[정올/JUNGOL] 1374번 긴 자리 덧셈 뺄셈 (C/C++)

 

2) compress (1자리 → 9자리)

반복 연산을 줄이기 위해 int 배열의 각 자리에는 1자리 씩이 아닌 9자리 씩 기록했습니다.
근데 9자리 수 * 9자리 수를 연산하면 최대 18자리 수가 만들어집니다.

18자리의 수는 int 로 처리가 안 되기 때문에
19자리까지 처리가 가능한 unsigned long long 으로 배열을 바꿨습니다. (2^64 = 18,446,744,073,709,551,616)

지금 생각해보니 곱셈 결과값의 자리 수가 unsigned long long int 로 처리되도록 잡아두고,
그 값을 2로 나눠서 각 자리를 9로 선정했어야 했는데.. 운 좋게 풀이가 된 케이스였습니다.

아무튼 위 2가지 설계를 반영하여, 이전 문제와는 다르게 BigInt 라는 구조체를 만들어서 풀었습니다.
구조체 덕분에 소스 코드가 깔끔하게 정리가 되었습니다.

struct BigInt {
	int len;
	int isMinus;
	ULL n[NLM];
} bn, bm, res;

 

3) 부호 처리

부호는 위 코드에서 확인할 수 있듯 구조체 내에 isMinus 라는 변수를 만들었고,
음수면 1, 양수면 0으로 처리했습니다.

곱셈의 결과(res) 의 부호는 두 수의 부호가 모두 양수(0)이거나 음수(1)이면 양수(0)이고
하나만 음수(1)이면 음수(1)가 됩니다.
그래서 처음에는 아래와 같이 작성했었습니다.

res.isMinus = (bn.isMinus - bm.isMinus != 0);

근데 글을 작성하다가 생각해보니 XOR 연산자로 깔끔하게 처리가 된다는 것을 알았습니다.
그래서 코드를 아래와 같이 수정했습니다.

res.isMinus = bn.isMinus ^ bm.isMinus;

이렇게 고친 이후 실행시간이 꽤나 큰 폭으로 줄었습니다. (58ms → 4ms)
Test case 중 단 한 번 뿐인 연산이라 약간 의아하지만..
어쨌든 성능이 중요한 시험을 치른다면 bitwise 를 적극 활용하는 것이 좋겠습니다.

 

4) 0 과 곱하는 경우

두 번째 수(m)가 0이면 곱셈 연산을 하지 않고 바로 res 를 m 으로 치환해주었습니다.
곱셈 연산을 직접해도 결과는 같지만 불필요한 연산을 하는 꼴이고
음수와 0을 곱할 경우 부호도 바꿔주어야 해서 그냥 덮어 씌우는 방식으로 처리했습니다.

그 외 풀이는 아래 코드 참고하시면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1262_긴 자리 곱셈
904 KB	4 ms
*/
#include <cstdio>

using ULL = unsigned long long;
const int LM = 207;
const int NLM = LM / 9;
const int BASE = 1000000000; // 10 ^ 9
char n[LM], m[LM];

struct BigInt {
	int len;
	int isMinus;
	ULL n[NLM];
} bn, bm, res;

int strlen(const char *a) {
	int len = 0;
	while (a[len]) ++len;
	return len;
}

void toBigInt(char *a, BigInt &bn) {
	int tmp = 0, idxN = 0, offset = 1;
	for (int i = strlen(a) - 1; i >= 0 && a[i] != '-'; --i) {
		tmp += offset * (a[i] - '0');
		offset *= 10;
		if (offset == BASE || i == 0 || a[i - 1] == '-') {
			bn.n[idxN++] = tmp;
			tmp = 0;
			offset = 1;
		}
	}
	bn.len = idxN;
	bn.isMinus = (a[0] == '-');
}

void multiply() {
	res.isMinus = bn.isMinus ^ bm.isMinus;
	res.len = bn.len + bm.len;

	for (int i = 0; i < res.len; ++i) res.n[i] = 0;

	for (int i = 0; i < bm.len; ++i) {
		for (int j = 0; j < bn.len; ++j) {
			res.n[i + j] += bn.n[j] * bm.n[i];
		}
	}

	for (int i = 0; i < res.len; ++i) {
		res.n[i + 1] += res.n[i] / BASE;
		res.n[i] %= BASE;
	}

	int i = res.len - 1;
	while (1) {
		if (i == 0 || res.n[i--]) break;
		--res.len;
	}
}

void printRes() {
	if (res.isMinus) printf("-");
	printf("%d", res.n[res.len - 1]);
	for (int i = res.len - 2; i >= 0; --i) {
		printf("%09d", res.n[i]);
	}
	puts("");
}

int main(){
#ifdef _WIN32
	freopen("1262.txt", "r", stdin);
#endif // _WIN32
	while (1) {
		scanf("%s %s", n, m);
		if (n[0] == '0') break;

		toBigInt(n, bn);
		toBigInt(m, bm);
		
		if (bm.len == 1 && bm.n[0] == 0) res = bm;
		else multiply();
		printRes();
	}
	return 0;
}