글 읽기 - 2729 이진수 덧셈 반례를 못 찾겠습니다.

hdnua 9년 전 0

BOJ 문제를 풀어보면서 BigInt 같은 걸 고민해본적이 있어

이진수의 덧셈은 간단하게 통과할 거라고 생각했는데

생각보다 제대로 되지 않습니다.

문자열을 뒤집는 strrev는 ANSI C 표준 함수가 아니라는 경고를 보고 mystrrev는 따로 구현했습니다.

수를 뒤집어 1의 자리부터 마지막 자리까지 계산하는 프로그램인데

어떤 부분에서 에러가 날까요? 주어진 입력도, 테스트한 몇 가지 결과도 정상적으로 나옵니다.

0 0: 0

0 1: 1

1 0: 1

1 1: 10

10 1: 11

1 10: 11

11 11: 110

10110 1001: 11111

1001 111: 10000

10101 1111: 100100

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_NUMBER_LEN = 82;
char a[MAX_NUMBER_LEN];
char b[MAX_NUMBER_LEN];
int c[MAX_NUMBER_LEN];

// strrev 경고에 따라 직접 작성 
void mystrrev(char *s) {
	char buf[256];
	strcpy(buf, s);
	char *end = buf + strlen(buf) - 1;
	while (end >= buf) {
		*s++ = *end--;
	}
}

int main(void) {
	int t;
	cin>>t;
	while (t--) {
		cin>>a>>b;
		// 1의 자리부터 자연스럽게 계산할 수 있게 문자열을 뒤집는다 
		mystrrev(a);
		mystrrev(b);
		// 긴 문자열, 짧은 문자열을 먼저 찾아놓는다 
		const int alen = (int)strlen(a), blen = (int)strlen(b);
		const int bigLen = max(alen, blen), smallLen = min(alen, blen);
		char *bigstr = (alen > blen) ? a : b;
		char *smallstr = (alen > blen) ? b : a;
		
		int i;
		int carry = 0; // 캐리 상태 저장 
		for (i=0; i<smallLen; ++i) { // 문자열의 길이가 서로 같은 동안 
			int result = (a[i]-'0') + (b[i]-'0') + carry;
			carry = result & 2 ? 1 : 0;
			c[i] = result & 1;
		}
		for (; i<bigLen; ++i) { // 남은 긴 문자열에 대해 처리한다 
			int result = (bigstr[i]-'0') + carry;
			carry = result & 2 ? 1 : 0;
			c[i] = result & 1;
		}
		// 처리하지 않은 캐리가 있다면 출력한다 
		if (carry) cout<<carry;
		// 답을 거꾸로 저장했으므로 출력할 때 뒤집어 출력한다 
		for (int j=i-1; j>=0; --j) {
			cout<<c[j];
		}
		cout<<endl;
	}
	return 0;
}

darkttd 9년 전 2

문제를 풀어보지는 않고, 코드와 문제만 보고 추론중에 다음과 같은 가능성을 제시해 봅니다.

입력이 "000 000" 이런식으로 불필요한 0 이 포함된채로 입력될 수 있지 않을까요?

hdnua 9년 전 1

아.. 그 부분이 문제였네요. 답변 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2729 이진수 덧셈 반례를 못 찾겠습니다.

hdnua 9년 전 0

darkttd 9년 전 2

hdnua 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말