[백준 21925번] 짝수 팰린드롬
문제 링크
https://www.acmicpc.net/problem/21925
문제 요약
길이가 \(N\)인 수열이 \(A\)가 주어진다. 수열 \(A\)를 길이가 짝수인 부분 수열들로 나눌 때, 짝수 팰린드롬을 최대한 많이 만드는 문제이다.
문제 풀이
이 문제는 부분 수열의 팰린드롬 여부를 미리 계산하는 전처리와 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다.
1. 부분 수열의 팰린드롬 여부를 미리 계산하기
부분 수열이 팰린드롬인지 여부를 나타내기 위해, boolean 타입의 2차원 배열 isPalindrome을 사용한다. 이 배열에서 isPalindrome[j][i]는 인덱스 \(j\)부터 \(i\)까지의 부분 수열이 팰린드롬인지를 나타낸다.
만약 가능한 모든 \(j\)와 \(i\)에 대해 \(A[j...i]\)가 팰린드롬인지 확인하려면, 각 구간을 하나하나 비교해야 하므로 시간 복잡도는 \(\mathcal{O}(N^3)\)이 된다. 이는 시간제한 내에 전처리를 할 수 없다는 문제가 있다.
이 문제를 해결하기 위해 팰린드롬의 특성을 이용할 수 있다. 팰린드롬이 성립하려면 양 끝이 같아야 하고, 그 안쪽 부분도 팰린드롬이어야만 한다. 즉, \(A[j...i]\)가 팰린드롬이려면 \(A[j +1 ...i - 1]\)도 팰린드롬이어야 한다는 의미다. 이 특성을 활용하면 전체 구간을 매번 비교하지 않고도 빠르게 팰린드롬 여부를 확인할 수 있다.
수열의 한 점 \(i\)와 \(i + 1\)을 기준으로 잡고 양쪽으로 확장해 가면서 팰린드롬 여부를 확인한다. 만약 중간에 팰린드롬이 아닌 경우가 나온다면, 양쪽을 더 확장한다고 하더라도 더 이상 팰린드롬인 부분 수열을 발견하지 못할 것이다. 이 방법은 \(\mathcal{O}(N^2)\)의 시간 복잡도를 가지기 때문에, 시간제한 내에 전처리를 완료할 수 있다.
void calcIsPalindrome() {
for (int i = 1 ; i <= n ; ++i) {
int lo = i, hi = i + 1;
while (lo >= 1 && hi <= n && A[lo] == A[hi]) {
isPalindrome[lo][hi] = true;
--lo;
++hi;
}
}
}
2. 동적 계획법으로 문제 해결하기
팰린드롬 여부를 미리 계산했으면, 동적 계획법(Dynamic Programming)을 사용해 최대 몇 개의 짝수 길이 팰린드롬으로 나눌 수 있는지 계산할 수 있다.
\(dp[i]\)를 수열의 첫 번째 인덱스부터 \(i\)번째 인덱스까지 짝수 길이 팰린드롬으로 분할할 수 있는 최대 개수라고 정의하자.
각 인덱스 \(i\)에 대해서, \(i\)보다 작은 모든 인덱스 \(j\)를 탐색한다. \(j\)부터 \(i\)까지의 부분 수열이 짝수 길이의 팰린드롬이라면, \(dp[i]\)를 \(dp[j - 1] + 1\)과 현재 값 중 큰 값으로 갱신한다. 이를 점화식으로 표현한다면 다음과 같다.
$$dp[i] = max(dp[i], dp[j - 1] + 1)$$
점화식을 코드로 옮길 때에는 부분 수열 \(A[...j - 1]\)이 짝수 팰린드롬으로 나눌 수 있는 경우인지 확인하는 것을 잊지 말자.
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 1 ; i <= n ; ++i) {
for (int j = i - 1 ; j >= 1 ; j -= 2) {
if (isPalindrome[j][i] && dp[j - 1] != -1) {
dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
}
}
소스 코드
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n, A[5010], dp[5010];
bool isPalindrome[5010][5010];
void calcIsPalindrome() {
for (int i = 1 ; i <= n ; ++i) {
int lo = i, hi = i + 1;
while (lo >= 1 && hi <= n && A[lo] == A[hi]) {
isPalindrome[lo][hi] = true;
--lo;
++hi;
}
}
}
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 1 ; i <= n ; ++i) {
for (int j = i - 1 ; j >= 1 ; j -= 2) {
if (isPalindrome[j][i] && dp[j - 1] != -1) {
dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1 ; i <= n ; ++i) {
scanf("%d", &A[i]);
}
calcIsPalindrome();
solve();
printf("%d\n", dp[n]);
}