백준 34587 (C++) Palindromic Distance

최초 업로드: 2025-10-25 19:17:36

최근 수정 시간: 2025-10-25 19:17:36

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] Palindromic Distance

[문제 링크](https://www.acmicpc.net/problem/34587)

## 문제 설명

The edit distance between two strings $u$ and $v$ is the minimum number of edit operations that turns $u$ into $v$. There are three edit operations that can be applied to a string: Insert a character, delete a character, and substitute some character by a different one.

For example, we can turn <code>hello</code> into <code>world</code> with four substitutions, so the edit distance is at most $4$. You can turn <code>wally</code> into <code>walter</code> with two substitutions and one insertion, so the edit distance is at most $3$. Computing the edit distance between two strings is a well-known problem with many applications.

The task at hand is to compute the edit distance of a string to one of the closest palindromes. A palindrome is a string that is the same when read backwards, for example madam.

The edit distance of <code>hello</code> to the closest palindrome is only $2$: We can turn <code>hello</code> into <code>ollo</code>, or <code>hllh</code>, or <code>elle</code> with two edit operations.

Write a program that can find the distance of a word to a closest palindrome.

## 입력

Each test contains multiple test cases. The first line contains the number of test cases $t$. The description of the test cases follows.

The only line of each test case contains a word $w$ consisting only of lowercase letters.

## 출력

For each test case, output the edit distance of the input word $w$ to its closest palindrome.

## 풀이
dp[L][R]을 L부터 R까지의 문자열을 팰린드롬이 되도록 하는 최소 연산 수로 두고 풀었다. 추가 연산은 의미가 없기에 삭제 연산과, 수정 연산만 사용하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

string s;
int dp[3000][3000]; // dp[L][R] : L부터 R까지 팰린드롬이도록 하는 최소 연산 수

int dfs(int l, int r) {
    if(l>=r) return 0;
    if(dp[l][r]!=-1) return dp[l][r];

if(s[l]==s[r]) dp[l][r] = dfs(l+1, r-1);
    else dp[l][r] = min({dfs(l+1, r), dfs(l, r-1), dfs(l+1, r-1)})+1;
    return dp[l][r];
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 cin >> s;
 for(int i=0;i<s.length();i++) for(int j=i+1;j<s.length();j++) dp[i][j]=-1;
 cout << dfs(0, s.length()-1) << '\n';
 }
}
```