boj 1695 팰린드롬 만들기

www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

입력으로 주어진 수열에 무작위로 수를 끼워넣어 팰린드롬으로 만드는데 최소 몇개의 수를 끼워 넣으면 되는지 구하는 문제입니다.

 

이 문제는 간단하게 주어진 수열과 뒤집은 수열의 lcs를 구한 후 N에서 뺀 값이 답입니다.

메모리 손해를 보지 않기위해 슬라이딩 윈도우 기법을 사용하였습니다.

 

 

#include <iostream>
#define max(a, b) {a > b ? a : b}
using namespace std;
 
int dp[2][5001], list[5001];
int N;
 
void func() {
    int t = 0;
    for (int i = N; i >= 1; i--) {
        for (int j = 1; j <= N; j++) {
            if (list[i] == list[j]) {
                dp[t][j] = dp[1 - t][j - 1] + 1;
            }
            else dp[t][j] = max(dp[1 - t][j], dp[t][j - 1]);
        }
        t = 1 - t;
    }
    
    cout << N - dp[1 - t][N] << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}