[C/C++] 백준 1509: 팰린드롬 분할 (DP)

1509: 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

팰린드롬?

 이 문제는 어떤 문자열을 팰린드롬으로 분할할 때 분할의 개수의 최솟값을 구해야하는 문제이다. 팰린드롬인지 아닌지는 10942: 팰린드롬? 문제와 같이 어떤 수가 팰린드롬일 때 양쪽끝(맨 처음과 맨 끝)을 제외한 가운데 부분도 팰린드롬이라는 사실을 이용하여 시간복잡도를 줄이며 확인할 수 있다. 그 과정은 아래 포스팅을 참고하면 된다!

https://donggul-godsang.tistory.com/101

[C/C++] 백준 10942: 팰린드롬? (DP)

 

알고리즘!

 그렇다면 관건은 찾은 팰린드롬들을 중복되지 않게 최소로 써 문자열을 구하는 것이다. 먼저 팰린드롬들을 저장하기 위해 vector<int> q1[2501]; 을 선언하고 팰린드롬이라면 left를 기준으로 right들을 저장해준다. 여기서 주의해야할 점은 단일 문자 즉, 'a'와 같은 경우도 팰린드롬이기 때문에 만약 문자열의 길이가 홀수가 될 경우 가장 가운데의 단일 문자도 팰린드롬이라고 저장을 해줘야한다.

 

 이제 중복되지 않게 최소로 팰린드롬을 써 문자열을 구하는 과정에 대해서 알아보자. 어떤 substring이 팰린드롬이고 마지막 index가 tmp일 때 tmp+1에서 시작하는 팰린드롬의 substring을 찾는 과정을 반복하면 된다. 이 반복되는 과정에서 시작부분과 끝부분을 mark[]배열에 저장을 했다.

 

이때 for문을 돌며 탐색할 때 mark[tmp]의 값이 0이 아니고 (이미 지나간 적이 있음). mark[tmp]<mark[i]+1(새로 들어온 경우의 수가 기존의 경우의 수보다 더 많은 팰린드롬을 써서 도달한 경우) 일 때는 건너뛴다. 예를 들어 q1에 (1,7),(1,4),(5,7)이 들어있을 때 (1,7)이 먼저 for문을 돌기 때문에 mark[8]=1이 되고 그 후 나란히 두 경우의 수가 들어오면 mark[5]=1, mark[tmp]=2(tmp는 8)이 되어 기존의 mark의 값보다 크게 되어 무시하게 되는 것이다.

 

이와 같이 진행을 하면 모든 팰린드롬의 경우의 수에 대해서 탐색을 하되, 가능성이 없는 경우에는 더 이상 진행을 하지 않아 굉장히 효과적인 알고리즘이 된다. 이렇게 q1에 있는 모든 팰린드롬 수를 돌려 mark[]배열을 돌리고 난 후 맨 마지막 mark[]배열에 들어있는 수가 곧 최소 부분 팰린드롬의 수가 되는 것이다.

 

주의해야할 점!

맨 처음 문제를 풀 때 팰린드롬의 길이가 긴 순으로 넣고 이미 지나간 곳은 못 넣게 구현하였는데 (Greedy) 이런 경우 예외가 발생하게 된다. 애초에 Greedy라고 확신하지 않았을 때에는 먼저 이 방법으로 구현하지 말고 모든 경우를 dp를 이용하여 어떻게 구현할지 생각을 계속해야할듯 하다.

 

 

 

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

string arr;
int mark[2501]; //분할의 최솟값을 구할 때 이용
int check[2501][2501]; //i부터 j까지 팰린드롬일때 i+1부터 j-1일까지 팰린드롬!
vector<int> q1[2501];

void calculate_min(int n,int cnt,int start){  
  for(int i=0;i<n;i++){
    for(int j=0;j<q1[i].size();j++){
      int tmp=q1[i][j]+1;
      if(mark[tmp]!=0 &&mark[tmp]<mark[i]+1)
        continue;
      mark[tmp]=mark[i]+1;
    }
  }
}
//https://www.acmicpc.net/board/view/109661

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>arr;
  int n=arr.length();
  for(int i=0;i<n;i++){
    for(int j=n-1;j>=i;j--){
      if(check[i][j]==1)
        continue;
      
      int string_len=(j-i+1)/2,left=i,right=j,alert=1;
      for(int k=1;k<=string_len;k++){ //팰린드롬인지 아닌지를 계산
        if(arr[left]!=arr[right]){
          alert=0;
          break;
        }
        left++, right--;
      }
      
      if(alert==1 || i==j) //팰린드롬이라면!
      {
        int tmp1=i, tmp2=j, tmp3=i-j;
        for(int k=1;k<=string_len;k++){
          check[tmp1][tmp2]=1;
          q1[tmp1].push_back(tmp2); //
          tmp2--,tmp1++;
        }
        if(tmp3%2==0){
           q1[tmp1].push_back(tmp1);
          check[tmp1][tmp2]=1;
        }        
      }
        
    }
  }
  
 int cnt=0;
  calculate_min(n,cnt,0);
  cnt=mark[n-1];
  cout<<mark[n];
  
}