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

 정보 올림피아드 알고리즘 1374번 긴 자리 덧셈 뺄셈

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

JUNGOL

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

 

1. 문제

두 개의 200자리 이하의 음이 아닌 정수를 입력받아서
두 수의 합과 차를 출력 (차는 큰 수에서 작은 수를 뺀 결과)

 

2. 풀이

unsigned int 는 2^32 이므로 0 ~ 4,294,967,296 - 1 (즉, 9자리까지 처리 가능, 10억은 4까지 밖에 못 쓰므로)
unsigned long long int 는 2^64 이므로 0 ~ 18,446,744,073,709,551,616 - 1 (즉, 19자리까지 처리 가능)

즉, 200자리 숫자의 사칙연산은 기본 변수형으로는 처리할 수 없습니다.
따라서 입력은 그대로 char 배열로 받은 뒤에 작은 숫자부터 올라가면서 계산하는 방식으로 풀었습니다.

하지만 숫자를 한 개씩 처리할 경우 최대 200회의 덧셈, 뺄셈 연산과
자리 올림, 내림 처리를 해야하므로 상당히 비효율적입니다.

그래서 입력받은 숫자를 9자리 씩 묶어서 계산하기로 했습니다.
(char 배열을 int 배열로 변환한다고 가정하면, 1칸에 9자리까지 숫자 표현 가능)

그리고 연산의 편의를 위해 int 배열로 변환할 때 가장 작은 9자리 숫자가 index 0에 오도록 했고,
그 다음 9자리를 index 1에, 그 다음 9자리를 index 2에 넣는 방식으로 거꾸로 기록했습니다.

변환 후 int 배열의 0번부터 끝까지 sum, minus 연산을 하는데,
덧셈 시 한 칸의 연산 결과가 9자리를 넘으면(1,000,000,000 이상이면) 다음 index 에 +1 을 해주었고,
뺄셈 시 한 칸의 연산 결과가 음수가 되면 다음 index 에 -1을 해주었습니다.

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

 

3. 디버깅

디버깅하면서 발견한 문제들 입니다.
혹시 디버깅에 도움이 될까 싶어 남깁니다.

 

1) leading 0 제거

뺄셈 연산의 경우 큰 수의 자리수를 그대로 사용하면 앞에 0이 남아있는 경우가 있습니다.
이를 그대로 출력하면 오답입니다. (ex. 200 - 199 는 1인데 001 로 출력함)
저는 뺄셈 연산을 마친 후 결과값 배열 중 가장 큰 수가 0이면, 출력할 res 배열의 길이를 1씩 줄이도록 처리했습니다.

int idx = rnlen - 1;
while (idx > 0) {
	if (res[idx]) break;
	--rnlen;
	--idx;
}

 

2) 숫자 중간에 00000000 이 있는 경우

이 부분은 디버깅으로 찾은건 아니고 1번을 반영하다가 같이 반영했습니다.
배열 중간에 leading 0 인 숫자가 있는데 그냥 %d 로 출력하면 자리수가 안 맞게 됩니다.
무조건 0을 채워서 9자리를 출력할 수 있도록 %09d 로 출력했습니다.
 
단, res 배열의 마지막 자리(가장 큰 수)는 %d 로 그대로 출력해야 불필요한 0이 찍히지 않습니다.

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

 

3) 덧셈 시 자리수 증가

90점에서 막혀서 한참 디버깅을 하다가 찾은건데
다음 숫자로 +1 은 잘 처리해놓고 출력할 결과 숫자 배열(res)의 길이(rnlen) 를 +1 하지 않아서 틀렸던 부분입니다.
이 문제는 sum 함수 종료 직전에 아래와 같은 코드를 넣어주어 해결했습니다.

rnlen += res[rnlen] > 0;

cf. 참고로 90점에서 오답인 경우 정답 값이 약간 짤려서 나옵니다. 실제 채점과는 무관하니 그냥 디버깅하시면 됩니다.

 

4. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1374_긴 자리 덧셈 뺄셈
904 KB	55 ms
*/
#include <cstdio>

const int LM = 207;
const int NLM = LM / 9;
const int BASE = 1000000000;
const int offset[] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
const int max(int a, int b) { return a > b ? a : b; }

char a[LM], b[LM];
int alen, blen;
int an[NLM], bn[NLM], res[NLM];
int anlen, bnlen, rnlen;

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

void convert(char *s, int *arr, int len, int *nlen) {
	int tempN = 0, cnt = 1, idxN = 0;
	for (int i = len - 1; i >= 0; --i) {
		tempN = (s[i] - '0') * offset[cnt++] + tempN;
		if (cnt == 10 || i == 0) {
			arr[idxN++] = tempN;
			tempN = 0;
			cnt = 1;
		}
	}
	*nlen = idxN;

	for (int i = idxN; i < NLM; ++i) arr[i] = 0;
}

void sum() {
	rnlen = max(anlen, bnlen);
	res[0] = 0;
	for (int i = 0; i < rnlen; ++i) {
		res[i] += an[i] + bn[i];
		res[i + 1] = res[i] / BASE;
		res[i] %= BASE;
	}

	rnlen += res[rnlen] > 0;
}

int compare() {
	if (alen != blen) return alen - blen;
	for (int i = anlen - 1; i >= 0; --i) {
		if (an[i] != bn[i]) return an[i] - bn[i];
	}
	return 0;
}

void minus(int *a, int *b, int anlen, int bnlen) {
	rnlen = anlen;
	res[0] = 0;
	for (int i = 0; i < rnlen; ++i) {
		res[i] += a[i] - b[i];
		if (res[i] < 0) {
			res[i + 1] = -1;
			res[i] += BASE;
		}
		else res[i + 1] = 0;
	}

	int idx = rnlen - 1;
	while (idx > 0) {
		if (res[idx]) break;
		--rnlen;
		--idx;
	}
}

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

int main(){
#ifdef _WIN32
	freopen("1374.txt", "r", stdin);
#endif // _WIN32
	while (1) {
		scanf("%s %s", &a, &b);
		if (a[0] == '0' && b[0] == '0') break;
		
		alen = strlen(a);
		blen = strlen(b);

		convert(a, an, alen, &anlen);
		convert(b, bn, blen, &bnlen);

		sum();
		printRes();
		if (compare() > 0) minus(an, bn, anlen, bnlen);
		else minus(bn, an, bnlen, anlen);
		printRes();

	}
	return 0;
}