백준 1695 팰린드롬 만들기 C++

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

1695번: 팰린드롬 만들기

간단한 dp 문제였지만 아이디어 떠올리기는 좀 힘들었습니다

 

dp[i][j] : i ~ j까지 부분 배열에 팰린드롬을 만들기 위해 필요한 최소 개수라 하면

입력된 배열을 arr 이라 할 때

arr[i] = arr[j] 이면 i, j 번쨰 값이 같으므로 i+1, j-1 번째까지 배열로 팰린드롬을 만드는데 필요한 개수와 같습니다.

그리고 arr[i] != arr[j] 이면, i+1 ~ j 번째까지 배열로 팰린드롬 만드는데 필요한 개수와 i ~ j-1 번째까지 배열로 팰린드롬 만드는데 필요한 개수 중 최소값을 고르고 +1 (arr[i], arr[j] 에 해당하는 값) 을 해주면 됩니다.  

따라서 최종적으로 dp 가 다음과 같이 정의됩니다.

dp[i][j]

= dp[i+1][j-1] if arr[i] == arr[j],

   min(dp[i+1][j], dp[i][j-1]) +1 otherwise

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int arr[5001];
int dp[5001][5001];

// dp[i][j] : i~j 인 부분 배열에서
// 필요한 최소 개수
// arr[i] = arr[j] : dp[i][j] = dp[i+1][j-1]
// else : dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

void init()
{
  cin >> n;
  memset(arr, 0, sizeof(arr));
  memset(dp, 0, sizeof(dp));
  
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
}

int calc(int i, int j)
{
  // 계산 완료
  if(dp[i][j] != 0)
    return dp[i][j];

  // 펠린드롬 필요 없는 경우
  // 에러 처리 겸용
  if(i >= j)
    return 0;
  
  if(arr[i] == arr[j]) {
    dp[i][j] = calc(i+1, j-1);
  }
  else {
    dp[i][j] = min(calc(i+1, j), calc(i, j-1)) + 1;
  }

  return dp[i][j];
}

int main() 
{
  init();
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      calc(i, j);
    }
  }

  cout << dp[0][n - 1];
}