[정올/JUNGOL] 3115번 긴 자리 나눗셈 (C/C++)

정보 올림피아드 알고리즘 3115번 긴 자리 나눗셈

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

JUNGOL

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

 

1. 문제

두 개의 200자리 이하의 양의 정수를 입력받아서

큰 수를 작은 수로 나눈 몫을 출력

 

2. 풀이

긴 자리 수 사칙연산의 최종 버전이라고 할 수 있는 문제입니다.

① 긴 자리 덧셈 뺄셈, ② 긴 자리 곱셈 문제를 푼 후에 이 문제를 풀 것을 권장드립니다.

 

https://rightbellboy.tistory.com/145

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

https://rightbellboy.tistory.com/146

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

 

나눗셈 문제도 큰 틀에서의 해결 과정은 위 2개 문제와 비슷합니다.

(200자리 숫자를 int 배열로 변환하고 역순으로 저장한 뒤 연산하는 방식)

 

다만 덧셈, 뺄셈, 곱셈과는 다르게 단순하게 작은 자리 수 부터 연산하는 방식으로는 풀리지 않습니다.

왜냐하면 제수(나누는 수)도 최대 200자리의 긴 자리 숫자이므로

나눗셈 기호(/) 를 사용하여 직접 연산하는 방식으로는 풀 수 없기 때문입니다.

 

그래서 처음에는 피제수가 0보다 작아질 때 까지 [피제수 빼기 제수] 를 반복한 뒤

반복 횟수를 출력하는 방식을 생각해봤습니다.

하지만 출력 예시만 봐도 억 단위를 훌쩍 넘기 때문에 제한 시간인 1초 안에 해결이 안 될 것이 분명했습니다.

 

그러던 중 백준에서 6974번 Long Division 이라는 문제를 발견했는데

해당 문제에서 제시한 아래와 같은 방법처럼 제수를 왼쪽으로 Shift 하여 빼는 방식으로 풀어보았습니다.

 

divide 라는 함수에서 전체적인 나눗셈 연산을 처리하는데,

왼쪽으로 Shift 하면서 변경할 제수를 t 라고 선언한 뒤 위 방식을 그대로 구현해서 풀었습니다.

 

앞선 2문제(덧셈 뺄셈, 곱셈)를 풀었다면 이 문제는 이정도 설명으로도 충분할 것 같습니다.

나머지 풀이는 아래 코드로 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
3115_긴 자리 나눗셈
904 KB	57 ms
*/
#include <cstdio>

const int LM = 210;
const int NLM = LM / 8;
const int BASE = 100000000;

char n[LM], m[LM];

struct BigInt {
	int len;
	int n[NLM];
} bn, bm, q, zero;

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

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

int compare(BigInt &a, BigInt &b) {
	if (a.len != b.len) return a.len - b.len;
	for (int i = a.len - 1; i >= 0; --i) {
		if (a.n[i] != b.n[i]) return a.n[i] - b.n[i];
	}
	return 0;
}

void multiplyTen(BigInt &a) {
	for (int i = 0; i < a.len; ++i) a.n[i] *= 10;
	for (int i = 0; i < a.len; ++i) {
		a.n[i + 1] += a.n[i] / BASE;
		a.n[i] %= BASE;
	}
	a.len += (a.n[a.len] > 0);
}

void divideTen(BigInt &a) {
	for (int i = 0; i < a.len; ++i) {
		a.n[i] /= 10;
		a.n[i] += (a.n[i + 1] % 10) * BASE / 10;
	}
	a.len -= (a.n[a.len - 1] == 0);
}

void subtract(BigInt &a, BigInt &b) {
	for (int i = 0; i < a.len; ++i) {
		a.n[i] -= b.n[i];
		if (a.n[i] < 0) {
			a.n[i] += BASE;
			a.n[i + 1] -= 1;
		}
	}
	a.len -= (a.n[a.len - 1] == 0);
}

void divide(BigInt &a, BigInt &b) {
	BigInt t = b;
	while (compare(a, t) > 0) multiplyTen(t);
	
	while (1) {
		while (compare(a, t) >= 0) {
			subtract(a, t);
			++q.n[0];
			if (q.len == 0) ++q.len;
		}
		divideTen(t);
		if (compare(t, b) < 0) break;
		multiplyTen(q);
	}
}

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

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

		toBigInt(n, bn);
		toBigInt(m, bm);

		if (compare(bn, bm) >= 0) divide(bn, bm);
		else divide(bm, bn);

		printRes();
	}
	return 0;
}