백준 1695번 : 팰린드롬 만들기

  팰린드롬 관련 문제를 예전에 푼 적이 있어서 조금 더 수월하게 풀었던 것 같다. 그때는 팰린드롬인지 아닌지를 판별하는 문제였지만 이번에는 팰린드롬이 되기 위해서 숫자가 얼마나 더 필요한지에 대한 문제였다.

---

  풀이

  dp 문제는 dp를 잘 정의하면 반은 먹고 들어간다.

 

dp [a][b] : a부터 b까지의 부분 수열을 팰린드롬으로 만들기 위해 끼워 넣어야 할 숫자의 최소 개수

 

  dp를 잘 정의했다면 그다음은 이 dp를 어떻게 확장 또는 축소시켜나갈지를 고민하면 된다.

 

a번째 수열의 수와 b번째 수열의 수가 같다면 dp [a][b] = dp [a+1][b-1]

 

  팰린드롬을 만들려고 하는 것이기 때문에 시작 수와 끝 수가 같다면 범위를 줄여나갈 수 있다. 그러면 다르다면 어떻게 될까?

 

a번째 수열의 수와 b번째 수열의 수가 다르다면 dp [a][b] = min(dp [a+1][b], dp [a][b-1]) + 1

 

  다르다면 팰린드롬으로 맞춰주기 위해서 숫자를 끼워 넣어야 한다. 이때 두 가지 경우의 수가 있다. a번째 수열에 대응하도록 제일 뒤쪽에 수를 넣는 방법과 b번째 수열에 대응하도록 제일 앞쪽에 수를 넣는 방법이 있다. 끼워 넣는 숫자의 개수를 최소화하고 싶으므로 min함수를 이용해서 둘 중 작은 값을 택한다. 그리고 어찌 됐는 팰린드롬으로 만들기 위해서는 숫자 하나를 추가해야 하기 때문에 1을 더해준다.

---

  초기화 및 계산

  dp를 위와 같이 정의하면 dp [2][2] 같은 값은 0이 되어야 한다. 따라서 dp에서 자주 쓰이는 0이면 계산하고 0이 아니면 계산하지 않는다 같은 테크닉을 쓸 수가 없다. 대신 dp의 기본값을 -1로 초기화시켜준 후 -1이면 계산하고 -1이 아니면 계산하지 않는다를 사용했다.

 

  또한 계산할 때 단순히 이중 for문으로만 하기 어려워서 dfs와 같은 재귀 형식을 채택했다. pelin(a, b)를 계산할 때 a와 b가 같으면 추가해야 할 숫자는 없고, a가 b보다 큰 경우는 있어서는 안 되므로 그때도 0을 리턴했다.

 

#include <iostream>

using namespace std;

int n;
int seq[5002];
int dp[5002][5002];

int pelin(int a, int b)
{
    if(dp[a][b] != -1) return dp[a][b];
    if(a >= b)
    {
        dp[a][b] = 0;
        return dp[a][b];
    }
    
    if(seq[a] == seq[b]) dp[a][b] = pelin(a+1, b-1);
    else dp[a][b] = min(pelin(a, b-1), pelin(a+1, b)) + 1;
    
    return dp[a][b];
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> seq[i];
        for(int j = 0; j < n; j++)
        {
            dp[i][j] = -1;
        }
    }
    
    
    for(int i = 0; i < n-1; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            pelin(i, j);
        }
    }
    
    cout << dp[0][n-1];

    return 0;
}