BOJ 1053 - 팰린드롬 공장

BOJ 1053 - 팰린드롬 공장

[분류 - 다이나믹 프로그래밍]

 

[풀이]

  4번 연산이 엄청 까다로워 보인다. 하지만 딱 한 번만 사용할 수 있으니 이에 대해 전처리를 진행해보자
1. 4번 연산을 사용하지 않는다.
2. 4번 연산을 사용한다(swap(s[i], s[j]), i != j).

  나머지 연산에 대해서 생각해보자.
  최소 연산수를 만족하기 위해서 삽입을 하거나, 삭제를 하거나, 특정 문자로 교환하는 행위는 반드시 팰린드롬을 만들기 위해 이득이 되어야한다. 다시 말하면 연산을 진행했을 때, 결과 팰린드롬의 일부가 반드시 되어야한다.

  양끝부터 시작해서 팰린드롬 연산을 진행한다. 이 과정은 위의 4번 연산을 쓸 때와 안 쓸 때에 모두 계산이 필요하다.

dp[l][r] = 구간 [l, r]에 대해 팰린드롬을 만들기 위한 최소 연산 수

 

  위 수식을 토대로 아래 경우를 고려하여 다이나믹을 구성해주면 되겠다.
1. 만약 s[l] == s[r]이라면 dp[l+1][r-1]에 대해 부분 문제를 가져올 수 있다.
2. 모든 경우에 대해 dp[l+1][r], dp[l][r-1]에 대해 부분 문제를 가져올 수 있다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 50;
char s[51];
int dp[MAX_N][MAX_N];
int rec(int l, int r) {
    if (l >= r) return 0;
    int& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = 1e9;
    if (s[l] == s[r])
        ret = rec(l + 1, r - 1);
    ret = min({ ret, rec(l + 1, r) + 1, rec(l, r - 1) + 1 });
    return ret;
}
int main() {
    scanf("%s", s);
    int L = strlen(s), i, j, answer;

    memset(dp, -1, sizeof dp);
    answer = rec(0, L - 1);

    for (i = 0; i < L; i++) for (j = i + 1; j < L; j++) {
        swap(s[i], s[j]);
        memset(dp, -1, sizeof dp);
        answer = min(answer, rec(0, L - 1) + 1);
        swap(s[i], s[j]);
    }
    printf("%d", answer);
    return 0;
}