Boj 1509 c ++ 팰린드롬 분할

팰린드롬 분할 Gold 1

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

 

 

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

최솟값을 묻고 있다. 그럼 뭐다? 그리디 아니면 dp다.

그런데 이 문제의 경우에는 작은 부분이 큰 부분에 영향을 주기 때문에 dp이다.

 

점화식을 어떤식으로 세우면 좋을까?

 

우선은 각각의 부분이 팰린드롬인지 아닌지 판단해야 할 듯하다.

이전의 풀었던 팰린드롬? 문제의 점화식을 참고하자. 10942

 

어떤 문자열이 팰린드롬인지 아닌지 판별하기 위해서는 범위를 지정해주어야 한다.

문자열의 시작지점을 S, 끝나는 지점을 E라고 하자. 기본적으로 S와 E는 같아야 한다.

그리고 S+1, E-1 지점까지의 문자열 또한 팰린드롬이여야 한다.

간격이 1인 문자열의 경우, 예외처리를 해주어야 한다.(S, E 지점이 엇갈리므로)

각각의 문자(길이가 1인 문자열, 즉 S == E인 문자열)은 모두 팰린드롬이다.

 

이러한 논리를 바탕으로 우리는 문자열의 모든 부분에 대하여 팰린드롬 여부를 저장한 dp배열을 얻게 된다.

 

    for(int i = 1; i <= N; i++){
        dp[i][i] = 1;
    }
    for(int i = 1; i < N; i++) {
        for(int j = 1; i+j <= N; j++) {
            int S, E;
            S = j;
            E = i+j;
            if(arr[S] != arr[E])
                continue;
            if(dp[S+1][E-1] == 1 || (S+1 == E))
                dp[S][E] = 1;
        }
    }

여기서 i 는 간격, j는 시작지점을 의미한다.

간격이 좁은 것들 부터 저장하는 것이 유리하다는 논리 하에 작성한 코드.

 

 

 

최종적으로 구해야 하는 값은 해당 문자열을 팰린드롬 분할 하기 위한 최소 횟수를 구하는 것.

그렇다면 두번째 dp배열의 정의는 'dp2[i] = i번째 인덱스까지의 문자열을 팰린드롬 분할 하기 위한 최소 횟수' 가 적당할 것 같다.

 

dp2 배열의 초기값은 해당 문자열의 길이로 설정해놓아야 한다. 최악의 경우 팰린드롬 분할 횟수는 문자열의 길이와 같기 때문이다.

점화식은 첫번째 dp배열, 팰린드롬 여부를 저장해놓은 값을 이용한다. 시작점이 작은 문자열 부터 순회하며 S E 간격의 문자열이 팰린드롬인지 확인한다.

S-E 문자열이 팰린드롬인 경우, 우리는 S - E 범위의 팰린드롬 분할 비용을 1로 치환할 수 있기에 다음과 같은 점화식이 성립한다.

 

'dp2[E] = min(dp2[E], dp2[S-1] + 1)'

 

이 방식으로 문자열의 각각의 인덱스에 대하여 최소 분할 비용이 모두 지정되게 된다.

 

정답 코드.

 

#include <iostream>
using namespace std;

int dp[2501][2501];
int dp2[2501];

int main() {
    int n;
    string s;
    cin >> s;
    n = s.length();

    for(int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for(int i = 1; i < n; i++) { //간격
        for(int j = 0; i+j < n; j++) { // 간격을 반영했을 때 끝값
            int S = j;
            int E = i+j;
            if(s[S] != s[E]) //시작과 끝 지점이 같은 경우에만
                continue;
            if(dp[S+1][E-1] || i == 1)  //가운데도 팰린드롬이거나 간격이 1인 경우
                dp[S][E] = 1;
        }
    }

    for(int i = 0; i < n; i++) {
        dp2[i] = i+1;
    }

    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {  //시작과 끝이 같은 경우 또한 정의
            if(dp[i][j] != 1)
                continue;
            if(i == 0) {
                dp2[j] = 1;
                continue;
            }
            dp2[j] = min(dp2[j], dp2[i-1] + 1); //dp[i-1] 값이 업데이트 되어있어야 한다
        }
    }
    cout << dp2[n-1];
}