[C++] 백준 2079 [팰린드롬]

접근방식

DP로 접근하면 되는 문제이다.
백준 10942와 연관된 문제이다.

풀이방법

anavolimilana 라는 문자열가 있다고 생각해보자.
이 문자를 팰린드롬으로 나누려면 처음 인덱스부터 팰린드롬이 되는 인덱스를 찾아줘야한다.
그 이후 재귀적으로 계속 줄여나가서 마지막 인덱스까지 모두 탐색하면 된다.

count_pal(string s, int count) 라는 함수가 있다고 하자. 이 함수는 s라는 문자열 안의 팰린드롬의 최소 갯수를 찾아주는 함수이다.
count_pal(anavolimailana, 0) 이 초기상태이고, a는 팰린드롬이기 때문에 count_pal(anavolimailana, 0) = count_pal(navolimailana, 1)로 나타낼 수 있다.

또한 ana도 팰린드롬이기 때문에, count_pal(anavolimailana, 0) = count_pal(volimailana, 1)로 나타낼 수 있다.
이 과정에서 중복되는 부분 문제가 생기기 때문에 DP로 해결해야한다.

이해하기 쉽게 count_pal의 매개변수를 string으로 정의해놨지만, 실제로는 인덱스를 매개변수로 하는 함수를 작성 할 것이다.

점화식 작성

일단, 백준 10942를 참고해서 is_pal()이라는 팰린드롬 판별 함수를 작성한다.
그 이후에 count_pal()이라는 팰린드롬의 최소 갯수를 나타내는 함수를 작성하면 된다.

count_pal(int start) = 문제에서 주어진 문자열의 start 인덱스부터 팰린드롬 문자열의 갯수이다.

count_pal()의 점화식은 다음과 같다.

for(int i=0; i<e-start+1; i++){
	if(is_pal(start, start+i)){
		ret = min(ret, count_pal(start+i+1)+1);
	}
}

여기서 e는 주어진 부분 문자열의 마지막 인덱스, start는 첫 인덱스이다.
첫 문자부터 마지막 문자까지 순회하면서 팰린드롬이 문자열을 찾으면 첫 인덱스를 찾은 문자열의 끝 인덱스+1로 옮겨서 다시 탐색하는 방법이다.

점화식의 초기조건

주어진 문자열의 마지막 문자까지 확인하고 나면 그 다음 인덱스로 count_pal이 호출된다. 그 때의 start는 e보다 크므로, 초기조건은

if(start > e) return 0;

로 정해주면 된다.

소스코드

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

int pal[2001][2001];
int cache[2001];
string s;
int e;
const int MAX = 987654321;

bool is_pal(int st, int e){
    if(st >= e) return true;
    int& ret = pal[st][e];
    if(ret == -1){
        ret = ((s[st] == s[e]) && is_pal(st+1, e-1));
    }
    return ret;
}

int count_pal(int start){
    if(start > e) return 0;
    int& ret = cache[start];
    if(ret == MAX){
        for(int i=0; i<e-start+1; i++){
            if(is_pal(start, start+i)){
                ret = min(ret, count_pal(start+i+1)+1);
            }
        }
    }
    return ret;
}

int main(){
    int result = MAX;
    for(int i=0; i<2001; i++){
        for(int j=0; j<2001; j++){
            pal[i][j] = -1;
            cache[i] = MAX;
        }
    }
    cin >> s;
    e = s.size()-1;
    cout << count_pal(0);
}