글 읽기 - 반례가 궁금합니다

kdk8361 6년 전 0

N보다 큰 팰린드롬 수 중 가장 작은 것을 구하는 것이므로 시작부터 1을 더해주고 중간(mid)을 기점으로 좌우로 나누어서 생각했습니다.

좌측(a)의 역(rev)을 취했을 때 우측(b)보다 크면 b에 수를 더해서 rev(a)를 만들어 팰린드롬으로 만들 수 있으므로 b=rev(a)를 넣습니다.

rev(a)<b인 경우 b바로 왼쪽의 자리++ 하게 되면 b가 0으로 채워져서 어떤 rev(a)라도 만들 수 있으므로

자리수가 홀수면 mid++, 짝수면 a++한 후 b=rev(a)를 하는 방식입니다.

접근방법 혹은 코드가 잘못되었거나 반례가 있다면 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <string.h>
#include <memory.h>

#pragma warning(disable:4996) 
using namespace std;

string s, a, b, mid;
string arev;
int slen;

pair<string, bool> spp(string temp) {
	int temp_len = temp.length();
	int t = temp_len - 1;
	bool l_carry = false;

	if (temp[t] != '9')
		temp[t] += 1;
	else {
		while (t >= 0 && temp[t] == '9') {
			temp[t] = '0';
			t--;
			if (t < 0) l_carry = true;
		}
		if(!l_carry) temp[t] += 1;
	}
	return make_pair(temp, l_carry);
}

string rev_s(string temp) {
	int len = temp.length();
	string t1;
	for (int i = len - 1; i >= 0; i--) {
		t1 += temp[i];
	}
	return t1;
}

int main()
{
	cin >> s;
	pair<string, bool> init = spp(s);
	s = init.first;
	if (init.second) s = '1' + s;
	slen = s.length();

	a = s.substr(0, slen / 2);
	b = s.substr((slen + slen % 2) / 2, slen / 2);
	mid = s.substr(slen / 2, slen % 2);
	
	arev = rev_s(a);

	int re = arev.compare(b);
	if (re == -1) {
		if (mid.length() == 0) {
			a = spp(a).first;
		}
		else {
			pair<string, bool> temp = spp(mid);
			mid = temp.first;
			if (temp.second) a = spp(a).first;
		}
		b = rev_s(a);
	}
	else if (re == 1) {
		b = arev;
	}
	if(mid.length() == 0) cout << a + b << '\n';
	else cout << a + mid + b << '\n';

	return 0;
}

simm4256 6년 전 1

한자리 수는 그대로 출력하셔야 합니다.

문제는 저도 94퍼에서 틀렸네요. 끙...

kdk8361 6년 전 1

N보다 큰 팰린드롬 수 중에서 가장 작은걸 구하는거기 때문에 N은 제외하는거 아닌가요?

simm4256 6년 전 2

전 바보였습니다.

질문 글에서 오히려 제가 해답을 얻고 가네요....

덕분에 맞았으니 이번엔 이 코드의 반례를 찾도록 노력해보겠습니다.

psy1125p 6년 전 0

+1 하는거 덕분에 맞췄습니다 감사합니다.

근데 50%에서 틀렷길래 이것저것 넣어보다가

9999999999 를 막 갈겨서 넣었더니 끝에 이상한문자가 하나 더 추가됫엇습니다.

저는 printf("%s",N) 를 for() printf("%c",N[]) 으로 하니까 맞았네요

혹시 이런문제일수도 있으니 확인해보세요 !

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

문제

문제

출처

ICPC

반례가 궁금합니다

kdk8361 6년 전 0

simm4256 6년 전 1

kdk8361 6년 전 1

simm4256 6년 전 2

psy1125p 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말