[Pro][정올] 1262번 : 긴 자리 곱셈

[Pro][정올] 1262번 : 긴 자리 곱셈 

JUNGOL

 

 

[풀이 후기]
난이도 : ★★★☆ (Pro)
문제 종류 : 긴 자리 연산
해결 방법 : Compression

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

---

 

문제

 

 

 

 

문제분석

1. 100 자리 이하의 두 정수가 입력된다. 

2. 두 수를 곱한 결과를 출력하면 된다. 

3. 100 자리의 두 정수를 곱하면 최대 200자리까지 결과가 나올 수 있다. 

 

---

 

접근 방법

이 문제의 핵심은 "어떻게 100자리의 두 수를 곱할 것인가?" 이다. 

 

이전 포스팅의 "긴 자리 덧셈" 문제에서도 말했듯이, 

단순히 int나 long long 으로 선언된 변수로는 100자리의 정수를 다룰 수 없다.

따라서, 100자리의 char 배열로 그대로 곱셈을 해야한다. 

 

[Pro][정올] 1374번 : 긴 자리 덧셈

 

 

 

 

먼저, 곱셈을 진행하는 과정을 살펴보자. 

곱셈은 아래와 같이 가장 낮은 자리의 수부터, 곱셈을 B[ ] 자리수만큼 진행하고, 그 결과를 SUM하는 방식이다. 

 

8자리 수의 곱셈 예시

 

 

그런데, 최대 100자리의 두 수가 주어지게 되므로, 

100번의 곱셈이 진행된 이후에, 최대 200번의 덧셈 작업을 추가로 수행해야 곱셈이 완성된다. 

좀 더 적은 반복 횟수로 연산을 진행할 수는 없을까?

 

이전의 긴자리 덧셈, 뺄셈에서 진행한 것과 동일하게, 8자리씩 묶어서 곱셈을 진행해보자. 

 

[Pro][정올] 1374번 : 긴 자리 덧셈 뺄셈

[Pro][정올] 1374번 : 긴 자리 덧셈 뺄셈

 

 

 

 

 

다만, 주의해야할 점은 8자리를 묶은 수를 int로 표현하면, 곱셈을 진행했을 때, int의 범위를 벗어나게 된다. 

그러므로, long long을 사용하자. 

(int는 최대 2,147,483,647까지 표현이 가능하므로, 10자리까지만 표현이 가능하다. 따라서, 8자리 곱셈에서 최대로 나올 수있는 16자리를 표현 못한다. )

 

8자리로 압축하여 곱셈

 

위의 예시에서 나온 8자리 수를 배열 1칸에 표현했더니, 단 1번의 연산만으로 곱셈을 할 수 있게 되었다. 

우리는 이 방법으로 8배 빠른 곱셈을 진행할 수 있게 되었다. 

 

---

 

코드

#include <cstdio>
#define COMP_DIGIT 8

using LL = long long;
const int LM = 1000;
const int NLM = LM / COMP_DIGIT + 1;
const int BASE = 100'000'000;	// 8자리 압축

char as[LM + 5], bs[LM + 5];

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

struct BigInt {
	LL num[NLM];	// Compressed Num
	int len, sign;	// num[] 의 길이

	void init() {
		for (register int i = 0; i < NLM; i++) num[i] = 0;
		len = 1, sign = 0;	// 0 : 양수 or 0, 1 : 음수
	}

	BigInt() { init(); }

	BigInt(const char *s) {
		init();

		if (s[0] == '-')	// 음수인 경우, 문자열에서 제거하고 sign 표시
			s++, sign = 1;

		int slen = strlen(s) - 1;
		len = (slen + COMP_DIGIT) / COMP_DIGIT;

		LL d = 0;
		for (register int i = slen; i >= 0; i--) {	// 문자열 왼쪽부터 정수화
			d = d * 10 + s[slen - i] - '0';
			if (i % COMP_DIGIT == 0) num[i / COMP_DIGIT] = d, d = 0;	// 압축 BIT로 나눠떨어질 때, num[]에 저장
		}
	}

	bool isZero() {
		return len == 1 && num[0] == 0;
	}

	void multi(BigInt &b) {
		if (isZero() || b.isZero()) {	// 둘 중에 하나라도 0인경우
			init();
			return;
		}

		sign ^= b.sign;	// 부호가 다르면 1, 같으면 0

		LL ret[LM] = { 0 };			// 곱셈 중간 결과 저장할 ret[]
		register int rlen = len + b.len - 1;	// ret[] 길이
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < b.len; j++) {
				ret[i + j] += num[i] * b.num[j];	// 곱셈 중간 결과 기록
			}
		}

		for (int i = 0; i <= rlen; i++) {
			ret[i + 1] += ret[i] / BASE;	// 자리 올림처리
			num[i] = ret[i] % BASE;		// 곱셈 결과를 num[]에 저장
		}
		len = rlen + (ret[rlen] > 0);	// 자리올림으로 자리수가 늘어났을 수 있음
	}

	void toString(char *ret) {
		register int i = len - 1, j = 0;	// i: num[] index, j:ret[] index
		if (sign) ret[j++] = '-';	// 음수 부호 처리

		// 1. num[]의 맨 뒤 숫자를 s[]에 write
		LL d = BASE, n = num[i--];
		for (; d > 1 && n / d == 0; d /= 10);
		for (; d; d /= 10) {
			ret[j++] = (char)(n / d + '0');
			n %= d;
		}

		// 2. num[]의 나머지는 오른쪽부터 8자리씩 s[]에 write
		for (; i >= 0; i--) {
			n = num[i];

			// loop unrolling
			ret[j + 7] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 6] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 5] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 4] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 3] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 2] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 1] = (char)(n % 10 + '0'), n /= 10;
			ret[j + 0] = (char)(n % 10 + '0'), n /= 10;
			j += 8;
		}
		ret[j] = 0;
	}

}mul, operand;

// 합: sum += operand
// 차: diff -= operand
// 곱: mul *= operand

int main() {
	while (scanf("%s %s", as, bs)) {
		mul = BigInt(as);
		operand = BigInt(bs);

		if (mul.isZero()) break;

		mul.multi(operand);

		mul.toString(as);	// 첫번째 배열에 곱셈 결과 저장

		puts(as);
	}
	return 0;
}

 

 

 

---

 

제출 결과

정올 1262번 제출 결과