[Pro][정올] 3115번 : 긴 자리 나눗셈

[Pro][정올] 3115번 : 긴 자리 나눗셈 

JUNGOL

 
 

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

 

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

---

 

문제

 
 
 

문제분석

1. 200자리 이하인 두 개의 양의 정수가 입력된다. 
2. 두 정수 중, 큰 수에서 작은 수를 나눈 몫을 출력한다. 
 
 

---

 

접근 방법

이 문제의 핵심은 "어떻게 200자리의 두 정수를 나눌 것인가?" 이다. 
 
백준 6974번을 참고하여, 문제를 풀어보았다. 
아래 예시는 987654321 ÷ 3456789 에 대한 과정이다. 

백준 6974번의 나눗셈 수식

 
위 나눗셈의 과정을 풀어서 설명해보겠다. 
1. 제수와 피제수의 자리수를 맞추기 위해서, 제수인 3456789 에다가 100을 곱해서, 345678900을 만든다. 
2.  987654321 > 345678900 이므로, 987654321 - 345678900 = 641975421 을 계산한다.  - (1) First successful subtraction
3. 641975421 > 345678900 이므로, 641975421 - 345678900 = 296296521 을 계산한다.  - Second successful subtraction
4. 296296521 < 345678900 이므로, 뺄셈을 하게 되면 음수가 나온다.  - unsuccessful subtraction
5. 296296521 보다 값이 작아질때까지 345678900 을 10씩 나눈다. 
6. 296296521 > 34567890 이므로, 뺄셈을 해도 양수가 나온다.  - (2)
7. 위의 과정을 반복하고, 제수가 처음의 수보다 작아지면 종료한다. 
 
 
 
 
추가로, 이전 포스팅에서 다뤘던 것처럼, 8자리씩 묶어서 나눗셈을 진행하면, 8배 빨라진 연산을 수행할 수 있다. 
 

8자리씩 묶어서 나눗셈 수행

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

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

 

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

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

 
 
 
 

---

 

코드

#include <stdio.h>

const int LM = 205;
const int CLM = 26;				// 10진수 8개 묶음
const int BASE = 100'000'000;	// 10진수 8개 묶음

char str_n[LM], str_m[LM];

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

int numCmp(int* numA, int lenA, int* numB, int lenB) {	// 양수 : A > B
	if (lenA != lenB) return lenA - lenB;
	register int i = lenA - 1;
	for (; i > 0 && numA[i] == numB[i]; i--);
	return numA[i] - numB[i];
}

struct BIGINT {
	int len;
	int num[CLM];

	void init() {
		for (int i = 0; i < CLM; ++i) num[i] = 0;
		len = 1;
	}

	BIGINT() {
		init();
	}

	void makeNum(const char* s) {		// 문자열을 10진수 8개씩 묶기
		int slen = strlen(s) - 1;	// 원래 문자열의 마지막 index
		len = (slen + 8) >> 3;		// 8개씩 묶고 나서의 길이

		int d = 0;
		for (register int i = slen; i >= 0; i--) {
			d = d * 10 + s[slen - i] - '0';		// 문자열 왼쪽부터 정수화
			if ((i & 0x7) == 0) {	// i % 8
				num[i >> 3] = d;
				d = 0;
			}
		}
	}

	void minus(BIGINT& b) {
		register int i = 0, n;
		for (; i < len; i++) {
			n = num[i] - b.num[i];
			if (n < 0) {
				n += BASE;
				num[i + 1]--;
			}
			num[i] = n;
		}
		len -= (num[len - 1] == 0);
	}
}answer, numA, numB, zero;

void multiplyTen(BIGINT& b) {
	for (register int i = b.len - 1; i >= 0; i--) {
		int n = b.num[i] * 10;
		b.num[i + 1] += n / BASE;
		b.num[i] = n % BASE;
	}
	b.len += (b.num[b.len] > 0);	// 자리수가 추가됨
}

void divideTen(BIGINT& b) {
	for (register int i = 0; i < b.len; i++) {
		b.num[i] /= 10;
		b.num[i] += (b.num[i + 1] % 10) * 10'000'000;
	}
	b.len -= (b.num[b.len - 1] == 0);	// 자리수가 감소함
}

void divide(BIGINT& a, BIGINT& b) {
	BIGINT tmpB = b;
	while (numCmp(a.num, a.len, tmpB.num, tmpB.len) > 0) multiplyTen(tmpB);	// A와 자리수 맞추기

	while (1) {
		while (numCmp(tmpB.num, tmpB.len, a.num, a.len) <= 0) {	// 제수 < 피제수 인 경우, 반복
			a.minus(tmpB);		// 뺄셈해서 몫 계산
			answer.num[0]++;	// 몫++
			//if (answer.len == 0) answer.len++;
		}

		divideTen(tmpB);
		if (numCmp(tmpB.num, tmpB.len, b.num, b.len) < 0) break; // tmpB < B 인 경우, 종료

		//answer.printNum();
		multiplyTen(answer);	// 몫 자리수 올리기
	}
}

void printAnswer() {
	printf("%d", answer.num[answer.len - 1]);
	for (register int i = answer.len - 2; i >= 0; --i) {
		printf("%08d", answer.num[i]);
	}
	puts("");
}

int main() {
	while (1) {
		scanf("%s %s", str_n, str_m);
		if (str_n[0] == '0' || str_m[0] == '0') break;	// 둘 중 하나라도 0이면 종료

		numA = numB = answer = zero;
		numA.makeNum(str_n);
		numB.makeNum(str_m);

		int cmpFlag = numCmp(numA.num, numA.len, numB.num, numB.len);
		if (cmpFlag > 0) {			// A > B
			divide(numA, numB);		// A / B
			printAnswer();		// 몫 출력 
		}
		else if (cmpFlag < 0) {		// A < B
			divide(numB, numA);		// B / A
			printAnswer();		// 몫 출력
		}
		else {						// A == B
			printf("1\n");
		}
	}
	return 0;
}

 
 
 

---

 

제출 결과

정올 3115번 제출 결과