[백준 1509번] 팰린드롬 분할 (C++)

문제링크 : https://www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int result[2501];
int dp[2501][2501];
string s;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> s;
    s = " " + s;
    for(int i=1; i<=s.size(); i++) //자기 자신 (1글자)
    {
        dp[i][i] = 1;
        if(s[i-1]==s[i] && i>1) dp[i-1][i]=1; //2글자인 경우(11, 22 등)
    }

     for(int i=s.size()-2; i>=1; i--) //3글자 이상인 경우
    {
        for(int j=i+2; j<=s.size(); j++) 
        {
            if(s[i]==s[j] && dp[i+1][j-1]) dp[i][j]=1;
        }
    }
    for(int i=1; i<s.size(); i++)
    {
        result[i]=MAX;
        for (int j = 1; j <=i; j++){
			if (dp[j][i]) result[i] = min(result[i], result[j - 1] + 1);
		}
    }
    cout << result[s.size()-1];

    return 0;
}

백준 10942 팰린드롬? 문제에서 응용이 추가된 문제이다.

팰린드롬 판별에 대한건 저번에 풀었으므로 이번 문제에선 생략하겠다.

참고 : https://blob-thinking.tistory.com/255

[백준 10942번] 팰린드롬? (C++)

이제 살펴봐야 하는 것은 팰린드롬을 체크하면서 최소값을 찾아주는 부분이다.

예시 : ABAD
j=1, i=1 : A
j=1, i=2 : AB / j=2, i=2 : B
j=1, i=3 : ABA / j=2, i=3 : BA / j=3, i=3 : A
j=1, i=4 : ABAD / j=2, i=4 : BAD / j=3, i=4 : AD / j=4, i=4 : D

위와 같이 문자의 앞부분 부터 확인하며 팰린드롬이 어디서 존재하는지 여부를 확인해준다.

현재 선택된 문자열 내에 (dp[j][i]) 팰린드롬이 존재한다면 이를 result 배열에 최소값을 담아준다.

 

기본적으로 결과값 저장은 result[j-1]+1을 통해 이루어진다.

현재 길이 내에서 현재 길이 전체가 팰린드롬이면 값이 1이 담길테지만(ex : AAA),

현재 길이 내에서 팰린드롬 수 여러개로 분할된다면(ex : ABC) 분할된만큼의 갯수가 결과값일 것이다.

<ABA>
A -> 팰린드롬 : A = 1
AB -> 팰린드롬 x / B -> 팰린드롬 : AB = 2 (1+1)
ABA -> 팰린드롬 / BA -> 팰린드롬 x / A -> 팰린드롬
A가 팰린드롬이고 그전 값 AB에 대해 저장된값 2가 있으므로 최종 값은 3이지만,
ABA가 팰린드롬이라 result[j-1]+1을 통해 (j=1) 1이 저장되어있으므로 최소값 탈락

<ABC>
A -> 팰린드롬 : A = 1
AB -> 팰린드롬 x / B -> 팰린드롬 : AB = 2 (1+1)
ABC -> 팰린드롬 x / BC -> 팰린드롬 x / C -> 팰린드롬 : ABC : 3 (1+1+1)

직전 문자가 팰린드롬 이었다면 result[j-1]에 저장된 값이 이미 있을 것이고, 그에 대해 +1을 추가해주게 되는 것이다.

처음에 가장 길이가 긴 값부터 초기화 해줌에 따라서 현재 i 범위 내에 팰린드롬이 최소가 되도록 판별을 해줄 수 있다.