백준) 1695 팰린드롬 만들기

1695. 팰린드롬 만들기

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

예제 입력 

5
1 2 3 4 2

예제 출력 

2

1. 접근

앞으로 보나 뒤로 보나 같은 수열을 팰린드롬 수열이라 한단다.

한 수열이 주어지고, 이 수열 양 끝과 사이사이에 숫자들을 끼워넣어서 팰린드롬으로 만들려고 한다.

이렇게 만드는 경우 중에 가장 숫자를 적게 쓰는 횟수는 몇번일까?

뭔가 획기적으로 수열을 분석하는 방법이 없으니까, (있을 수도 있지만 내가 모른당!)

무적의 다이나믹 프로그래밍으로 뚫어보자.

2. 풀이

가장 무식하게 팰린드롬으로 만드는 방법은 있다.

수열을 뒤집어서 뒤에 추가해 버리면 무조건 팰린드롬이다.

하지만 우리는 조각조각들을 끼워넣을 수 있으므로 저 방법보단 숫자들을 적게 쓴다.

그러면 무슨 패턴으로 숫자들을 추가해야 할까?

예시의 1, 2, 3, 4, 2 를 보자. 앞에서 보면 1의 짝꿍이 없으니까 뒤에 1을 추가해야 할 것 같긴 하다.

반대로 뒤에서 보면 2의 짝꿍이 없으니까 앞에 2를 추가해야 할 것 같기도 하다!

뒤에 추가하는 경우라면, 1은 짝이 생겼으니까 생각하지 않고, 남은건 2, 3, 4, 2로 팰린드롬을 만드는 문제다.

앞에 추가하는 경우라면, 2는 짝이 생겼으니까 생각하지 않고, 남은건 1, 2, 3, 4로 팰린드롬을 만드는 문제다.

아하! 그러면 앞에 추가하든지 뒤에 추가하든지 남은 수열의 문제 답이 작은 경우를 써야하겠다.

배열은 다음처럼 정의하자

DP[왼쪽 시작점][오른쪽 시작점] = DP[X][Y] = 남은 수열이 X~Y까지 수열일 때, 문제에서 원하는 정답을 저장

그러면 우리 답은 DP[0][N-1]에 있을 것이고,

기저사례들은 X>Y 가 되버려 수열을 다쓴 경우들이다.

X==Y인 경우도 당연히 더이상 뭘 해줄 필요는 사실 없지만, 원소가 두 개 남은 상태에서, 두 원소가 서로 다른 경우를 다시 생각해야 하는 번거로움이 있다. 그래서 기저사례는 저 경우만 생각하기로 하자.(푸는 사람 마음이다)

함수는 func(x, y)로 정의하고, DP[X][Y]를 계산해줘야 한다.

배열의 X번째 원소와 Y번째 원소가 같다면 둘다 무시하면 되고, 다르다면 뒤나 앞에 추가 해야 한다.

배열 크기에 시간 복잡도가 비례하니까, N*N = 25,000,000 으로 1초안엔 들어오겠다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, i;
int arr[5000];
int dp[5000][5000];
 
int func(int x, int y) {
    if (x > y)
        return 0;
 
    int& ref = dp[x][y];
    if (ref != -1)
        return ref;
 
    if (arr[x] == arr[y])
        return ref = func(x + 1, y - 1);
    else
        return ref = min(func(x + 1, y) + 1, func(x, y - 1) + 1);
}
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, n - 1));
 
    return 0;
}