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

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

JUNGOL

 

 

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

 

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

---

 

문제

 

 

 

 

문제분석

1. 두 개의 200자리 이하의 0 이상의 정수가 입력된다. 

2. 덧셈, 뺄셈 결과를 출력하면 된다. 

 

 

---

 

 

 

 

 

접근 방법

이 문제의 핵심은 "어떻게 200자리의 두 수를 더하고 뺄 것인가?" 이다. 

 

int로 선언된 변수는 4 Byte = 32bit 이므로, 2^31 범위인 –2,147,483,648 ~ 2,147,483,647 (10자리) 만 다룰 수 있다. 

long long으로 선언된 변수는 8 Byte = 48bit 이므로, 2^47 범위로 최대 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (19자리) 만 다룰 수 있다. 

 

따라서, 단순히 변수로는 안되고, 200자리 char 배열을 가지고  연산을 빠르게 처리할 수 있도록 해야한다. 

 

 

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

덧셈은 아래와 같이 가장 낮은 자리의 수부터, 덧셈을 진행하고, 올림이 발생하는 경우 높은 자리에 더해주면 된다. 

 

8자리 수의 덧셈 예시

 

 

 

그런데, 최대 200자리의 두 수가 주어지게 되므로, 반복문은 200번 수행해야 덧셈이 완성된다.

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

 

 

지금은 배열 1칸에 한자리 수만 표현이 되어있는데, 여러자리를 표현하면 어떨까?

int는 최대 2,147,483,647까지 표현할 수 있으므로, 8자리를 배열 1칸에 넣어보자. 

 

8자리로 압축하여 덧셈

 

 

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

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

 

---

 

코드

#include <cstdio>

const int LM = 205;
const int NLM = 205 / 8 + 1;
const int BASE = 100'000'000;	// 8자리 압축

char as[LM], bs[LM];
int strlen(const char*s, int len = 0) {
	for (; s[len]; ++len);
	return len;
}

struct BigInt {
	int num[NLM];	// Compressed Num
	int len, sign;

	// default값 만들기 긴자리 0
	void init() {
		for (int i = 0; i < NLM; ++i) num[i] = 0;
		len = 1;
		sign = 0;  // 0:양수 혹은 0, 1:음수
	}

	BigInt() { init(); }

	BigInt(const char*s) {
		init();
		if (s[0] == '-')
			++s, sign = 1;

		int slen = strlen(s) - 1;	// 문자열 길이 - 1 (-1하는 이유는 문자열이 0 base라서)
		len = (slen + 8) / 8;	// 8bit로 압축된 길이

		int d = 0;
		for (int i = slen; i >= 0; i--) {
			d = d * 10 + s[slen - i] - '0';		// 문자열 왼쪽부터 정수화하기
			if (i % 8 == 0) num[i / 8] = d, d = 0;		// 8비트로 나눠떨어지는 index가 되면, nun[] 오른쪽부터 저장
		}
	}

	bool isZero() { return len == 1 && num[0] == 0; }
	inline int max(int a, int b) { return a > b ? a : b; }
	inline int min(int a, int b) { return a < b ? a : b; }

	int arrcmp(int*ap, int alen, int*bp, int blen) {
		if (alen != blen) return alen - blen;  // 1순위: 길이가 긴것이 큰 수이다.
		int i = alen - 1;                      // 2순위: 길이가 같다면 높은 자리부터 비교한다.
		for (; i > 0 && ap[i] == bp[i]; --i);  //        같은 자리의 두수의 값이 다른 경우 또는 마지막 자리라면 종료
		return ap[i] - bp[i];                  // 음수(ap<bp), 0(ap==bp), 양수(ap>bp)
	}

	int plus(int*tg, int*ap, int*bp, int len) {
		for (int i = 0; i < len; ++i) {
			tg[i] = ap[i] + bp[i];
			tg[i + 1] += tg[i] / BASE;  // 자리올림 처리
			tg[i] %= BASE;
		}
		return len + (tg[len] > 0);
	}

	int minus(int*tg, int*ap, int*bp, int len) {
		for (int i = 0; i < len; ++i) {
			tg[i] = ap[i] - bp[i];
			if (tg[i] < 0)
				ap[i + 1]--, tg[i] += BASE;
		}
		int i = len - 1;
		for (; i > 0 && tg[i] == 0; --i);  // delete leading zero
		return i + 1;
	}

	void add(BigInt&b) {  // 계산 결과는 a에 저장된다.
		if (sign == b.sign) len = plus(num, num, b.num, max(len, b.len));
		else {
			int cmp = arrcmp(num, len, b.num, b.len);
			if (cmp < 0) len = minus(num, b.num, num, b.len);
			else if (cmp > 0) len = minus(num, num, b.num, len);
			else init();   // 두수가 같은 경우이므로 뺄셈의 결과는 0이다.
		}
	}

	void subtract(BigInt b) {
		b.sign ^= 1, add(b);
	}

	void toString(char*ret) {
		// 1. 숫자로 변환
		int i, j, k = 0, d;
		for (i = 0; i < len - 1; ++i) {
			d = num[i];
			for (j = 0; j < 8; j++) {
				ret[k++] = d % 10 + '0';
				d /= 10;
			}
		}
		d = num[i];
		while (d) {
			ret[k++] = d % 10 + '0';
			d /= 10;
		}
		if (k == 0) ret[k++] = '0';

		// 2. Reverse
		ret[k] = 0;		// sentinal value
		for (i = 0, j = k - 1; i < j; i++, j--) {
			char tmp = ret[i];
			ret[i] = ret[j];
			ret[j] = tmp;
		}
	}
}sum, diff, operand;
// 합: sum += operand
// 차: diff = abs(diff - operand)

int main() {
	while (scanf("%s %s", as, bs)) {
		sum = diff = BigInt(as);	// sum과 diff는 각각 더해지는 수, 빼지는 수
		operand = BigInt(bs);		// operand는 더하는 수, 빼는 수
		if (sum.isZero() && operand.isZero()) break;

		sum.add(operand);
		diff.subtract(operand);

		sum.toString(as);
		diff.toString(bs);

		puts(as);
		puts(bs);
	}
	return 0;
}

 

 

 

---

 

제출 결과

정올 1374번 제출 결과