BOJ(백준) 30400번 팰린드롬 제거

https://www.acmicpc.net/problem/30400

30400번: 팰린드롬 제거

매내처 알고리즘 응용 문제

 

처음에 문제를 해결한 방식은 다음과 같다. (조금 복잡한 방식이다 아래에 훨씬 단순한 방법이 있다.)

 

우선 매내처를 이용해 길이가 M인 팰린드롬 구간을 모두 찾는다.

각각의 구간들이 이러한 시작과 끝을 같는다고 하자.

 

구간 각각의 문자들 중에서 하나 이상의 문자가 파괴되기만 하면 조건을 만족하므로 우리가 구해야 될 것은 그림에서 최소 몇개의 수직선을 그어야 모든 구간을 통과할 수 있는가이다.

 

이것을 계산하기 위해서 우선 imos 알고리즘과 비슷하게 구간의 시작점과 끝점 모두를 시작점인지 끝점인지 표시하여 벡터에 넣어준다.

 

또한 벡터에 넣어 줄 때 각각의 구간에 고유한 번호를 매겨 함께 넣어준다. ({점의 위치, 시작점인지 끝점인지, 어떤 구간의 점인지}의 형태)

 

벡터를 정렬한다. 점의 위치를 기준으로 오름차순 정렬하되 위치가 같으면 시작점을 끝점보다 앞에 가게 한다.

 

그리고 특정 구간 번호를 인덱스로 그 구간에 선이 그어졌는지 확인하는 배열을 만들고, 구간 번호를 저장할 스택을 만든다.

 

이제 벡터를 앞에서부터 스위핑 하면서 만약에 구간의 시작점이라면 그 구간의 고유 번호를 스택에 푸쉬한다.

 

구간의 끝점이 들어온다면 그 구간에 선이 그어졌는지 체크한다. 만약 선이 그어지지 않았다면 스택에 있는 구간들 전부를 팝하면서 해당 구간에 선이 그어졌음을 표시하고 정답 값을 +1해준다.

 

스위핑이 끝나면 정답 값을 출력해주면 된다.

 

그러나 훨씬 더 간단한 방법이 존재한다.

 

매내처 알고리즘 진행 중에 길이가 M인 팰린드롬을 발견하면 그 팰린드롬의 가장 오른쪽 끝 문자를 부수는 것(=사용되지 않는 임의의 문자로 변경)이다.

 

이러한 방법이 가능한 이유는 우선 길이가 M이고 어떤 인덱스를 중심으로 하는 팰린드롬을 발견했을 때 만약 위의 방법을 사용하면 일단 인덱스의 왼쪽은 신경을 쓸 필요가 없다.

 

그러면 인덱스의 오른쪽만 조심하면 되는데 이 경우 오른쪽 끝을 부수면 인덱스의 오른쪽에서 가능한 모든 구간을 커버할 수 있다.

 

따라서 그리디하게 팰린드롬의 오른쪽 끝을 부수는게 해답이 된다.

 

AC code (첫번째 방법으로 푼 코드)

#include <bits/stdc++.h>
using namespace std;
int arr[400001],p,r,mx,s2[400001],N,K,sol,cnt,check[400001];
string s1;
vector<vector<int>> v;
vector<int> v2;

bool cmp(vector<int> &a,vector<int> &b) {
	if(a[0]!=b[0]) return a[0]<b[0];
	return a[1]>b[1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	cin>>s1;
	int len=s1.length();
	for(int i=0;i<len;i++) s2[2*i+1]=s1[i];
	for(int i=0;i<2*len+1;i++) {
		if(i<=r) arr[i]=min(r-i,arr[2*p-i]);
		while(s2[i-arr[i]-1]==s2[i+arr[i]+1]&&i-arr[i]-1>=0&&i+arr[i]+1<2*len+1) arr[i]++;
		if(i+arr[i]>r) {
			r=i+arr[i];
			p=i;
		}
		if(arr[i]>=K) {
			int t=K;
			if(arr[i]%2) {
				if(t%2) t--;
				int idx=(i-1)/2;
				v.push_back({idx-t/2,1,i});
				v.push_back({idx+t/2,0,i});
				
			} else {
				if(t%2) t++;
				int idx=(i-2)/2-(t/2-1);
				v.push_back({idx,1,i});
				v.push_back({idx+t-1,0,i});
			}
		}
	}
	sort(v.begin(),v.end(),cmp);
	for(auto i:v) {
		if(i[1]) v2.push_back(i[2]);
		else if (!check[i[2]]) {
			sol++;
			for(auto k:v2) check[k]=1;
			v2.resize(0);
		}
	}
	cout<<sol;
}

원래도 풀이 설명하는게 쉽지 않다고 생각했지만 이 문제가 유난히 더 어려운 것 같다.

 

설명에 이해가 안되는 부분이나 궁금하신 점이 있으면 언제든지 댓글로 물어봐주세요.

감사합니다.