BOJ 31572 팰린드롬 판별하기

문제 링크입니다.

Full Task만 설명하겠습니다.

쿼리 관찰하기

count_pair 쿼리의 결과로 얻을 수 있는 값은 0 , 1 , 3 뿐입니다. 각각 세 수가 모두 다른 경우, 두 수가 같은 경우, 세 수가 모두 같은 경우가 해당합니다.

문자열의 길이가 홀수인 경우

문자열의 길이가 짝수인지 홀수인지에 따라 가운데 원소의 유무가 다르고, 이것에 따라 전략을 다르게 구성할 필요가 있습니다.

문자열의 길이가 홀수라면, 가운데 원소를 제외한 나머지 원소가 대칭적이여야 합니다. count_pair 로 양쪽의 원소를 묶고, 나머지 하나는 그냥 가운데 원소로 통일해서 쿼리를 날려줍시다. 여기서 $\lfloor {N \over 2} \rfloor$개의 count_pair 가 소모됩니다.

• 0 이 반환된 경우: 양쪽 원소가 반드시 서로 다릅니다. 주어진 비밀 문자열 $S$는 팰린드롬이 아닙니다.
• 1 이 반환된 경우: 양쪽 원소가 서로 같거나, 둘 중 한쪽이 가운데 원소와 같습니다.
• 3 이 반환된 경우: 세 원소가 모두 같습니다. 그러므로 양쪽 원소는 반드시 같습니다.

1 이 반환된 경우들을 생각해 보면, 양쪽 원소가 서로 같은 경우는 반드시 가운데 원소가 양쪽 원소와는 다른 값을 가질 겁니다. 1 이 반환된 경우들 중 하나라도 가운데 원소와 같은 값을 가지는 경우가 있다면 비밀 문자열이 팰린드롬이 아닌 것이고, 아니면 팰린드롬인 상태가 됩니다. find_character 로 이를 확인해 주면 주어진 문자열이 팰린드롬인 지 판별할 수 있습니다.

문자열의 길이가 짝수인 경우

이번에는 가운데 문자가 없습니다. 하지만 그냥 있다고 생각하고 문제를 풉시다. 가운데의 두 원소 중 왼쪽을 가운데 원소라고 칩시다.

그러면 나머지 $N-2$개의 문자들로 홀수 길이 문자열에서 했던 걸 똑같이 해줍니다. 이때 소모되는 count_pair 의 수는 ${N-2 \over 2} = \lfloor {N \over 2} \rfloor -1$회이고, find_character 도 사용됩니다.

남은 2번의 count_pair 를 이용해 가운데의 두 원소가 같은 지를 판별해 줍시다.

• 이전 과정 중에 count_pair 의 결과로 3 이 반환된 적이 있다고 해봅시다. 그러면 내가 왼쪽 가운데 원소와 같은 값을 갖는 원소를 하나 알고 있으니, 그 두 원소와 오른쪽 가운데 원소가 같은지를 확인합시다.
• 이외의 경우, 모든 count_pair 의 결과로는 1 이 반환되었을 것입니다. 맨 왼쪽 원소와 가운데의 두 원소로 count_pair 를 날려줍시다. 이전 처리 과정에서 맨 왼쪽 원소의 값이 왼쪽 가운데 원소와는 달라야 한단 걸 알고 있으니 이번 쿼리의 결과로는 반드시 1이 반환돼야 합니다.
  • 이때 이 1 이 오른쪽 가운데 원소와 맨 왼쪽 원소의 쌍일 수 있습니다. 이를 확인해 주기 위해, 양 끝 원소와 가운데 오른쪽 원소로 count_pair 를 날려줍시다. 양 끝 원소가 서로 같아야 함을 알고 있고, 그 값이 오른쪽 가운데 원소와는 다를 것이므로 이 쿼리의 결과 또한 1 이 반환되어야 합니다.

이상의 내용을 그대로 구현하면 만점을 받을 수 있습니다.

코드

#include <vector>
using namespace std;

extern int count_pair(int, int, int);
extern int find_character(int, vector<int>);

vector<int> one;
int guess_palindromicity(int n){
	int three = -1;
	one.clear();
	for(int i = 0; i < (n-1)/2; i++){
		int qry = count_pair(i, (n-1)/2, n-1-i);
		if(qry == 0) return 0;
		if(qry == 3) three = i;
		if(qry == 1){
			one.push_back(i);
			one.push_back(n-1-i);
		}
	}
	if(~n&1){
	if(three < 0){
		int qry = count_pair((n-1)/2, (n+1)/2, 0);
		if(qry != 1) return 0;
		qry = count_pair(0, (n+1)/2, n-1);
		if(qry != 1) return 0;
	}
	else{
		int qry = count_pair((n-1)/2, (n+1)/2, three);
		if(qry != 3) return 0;
	}
	}
	return (one.empty() || !find_character((n-1)/2, one));
}