[Algorithm]Baekjoon 1695번 :: 팰린드롬 만들기

https://www.acmicpc.net/problem/1695

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int maxNum = 0x3f3f3f3f;
int n;
int arr[5001] = { 0 };
int dp[5001][5001] = { 0 };
 
int DFS(int left, int right)
{
    if (right - left < 1) return 0;
 
    int& result = dp[left][right];
    if (result != maxNum) return result;
 
    if (arr[left] == arr[right])
    {
        result = min(result, DFS(left + 1, right - 1));
    }
    else
    {
        result = min(result, DFS(left + 1, right) + 1); // 왼쪽 숫자를 오른쪽에 추가
        result = min(result, DFS(left, right - 1) + 1);
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    cout << DFS(1, n);
}
 
 
 

 

dp문제만 집요하게 푼 보람을 느낄 수 있었던 문제. 

침착하게 정석대로 잘 풀었다.

 

먼저 중복여부와 상관없이 완전탐색으로라면 어떻게 구할 수 있는가? 를 생각했다.

보아하니 양 끝 숫자가 다르면 반드시 숫자를 추가해야해서 하나를 삭제해줘야 하는데, 이 때 왼쪽숫자를 없앨지 오른쪽숫자를 없앨지에 대한 선택지가 2가지로 나뉜다. 

즉, 여기가 분기점인 것이다.

그대로 진행한다면 n은 최대 5000일테니, 크기의 절반만 2개의 분기점으로 검사하더라도 2^2500이라는 말도안되는 탐색횟수가 나온다.

 

그러면 중복되는부분이 어떤곳인지를 생각해야 한다.

처음 인풋으로주어지는 수열같은경우, arr의 1~n까지의 인덱스에 저장한다.

수열의 양 끝에서부터 하나씩 제거하면서 오기 때문에, arr에 저장된 수열의 인덱스가 변하거나 할 일은 없다.

예를들어 

 

인덱스 : 1 2 3 4 5

수열    :  1 2 3 4 2

 

이렇게 저장되어있다면, 수열의 가운데숫자인 3은 인덱스3에 계속 있다는 것이다.

2개의 분기점에 어떤선택을 하든 일관된 형태를 유지하기 때문에, 해당형태를 dp테이블의 기준으로 삼아도 되는것이다.

양 끝에서 깎기 때문에 left, right라는 왼쪽오른쪽 포인터를 두고 점차 깎아내릴것이며, 이 left right가 dp테이블의 기준이된다.

 

문제에서의 테스트케이스인 1,2,3,4,2로 친절히 설명해보겠다.

그렇다면 현재 left는 1, right는 5이다.

 

먼저 양 끝 1,2는 서로 다른 수이다.

그러면 오른쪽에 1을추가해서 왼쪽의 1을 제거하든지, 왼쪽에 2를 추가해서 오른쪽의 2를제거하든지 둘 중에 하나이다.

일단 오른쪽에 1을 추가해서 왼쪽의 1을 제거해본다. 추가했었기 때문에 +1을 카운팅해야한다.

여기서 숫자1을 추가했다는 것은, 추가했다고 치는것이다. 실제로 arr에 추가하거나 할 필요없다.

한쪽끝 숫자를 제거하기위해 추가횟수를 1카운팅하면서 추가한것처럼 하는 것 뿐이다.

 

어쨌든 그러면 수열은  X 2 3 4 2  가 된다. 왼쪽수를 제거했기 때문에 left에 +1을 더해준다.(그다음 수를 가리키게해야한다). dp테이블로 표현하면 dp[2][5].

그다음은 양끝이 숫자2로 같기때문에 추가할필요없이 그냥 제거해주면 된다.(33번째 라인)

양쪽을 제거했으니 left+1,right-1을 해준다.

 

그러면 X X 3 4 X 가 된다. dp테이블로 표현하면 dp[3][4].

여기선 오른쪽 수를 제거하든, 왼쪽수를 제거하든 동일하다.

코드상 왼쪽수를 먼저제거하는 코드이니, 4의 오른쪽에 3을 추가했다고 가정하고 3을 제거한다. 물론 횟수 +1카운팅.

그러면 4 한개만 남았기 때문에, 해당루트로의 탐색을 종료한다.