[C++] 백준 5502번 펠린드롬 풀이

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

5502번: 팰린드롬

 

문제

팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

 

풀이

이 문제는 LCS문제를 변형한 문제이다. 한 문자열이 펠린드롬이 되기 위해서는 펠린드롬이 되는 부분 문자열에 부족한 부분을 추가하면 된다. 따라서 어떤 문자열과 그 문자열을 뒤집은 문자열의 공통 부분 문자열의 길이를 구하고 원래 문자열과의 차이를 구하면 된다. 예시는 다음과 같다.

ab3bd를 뒤집으면 db3ba가 된다. 그럼 ab3bd와 db3ba의 공통 부분 문자열은 b3b가 된다. 그렇다면 원래 문자에서 빠진 문자는 a와 d가 있다. 이 a와 d를 원래 문자열에 하나씩 추가하면 펠린드롬을 만들 수 있는 것이다. 코드로 나타내면 다음과 같다.

 

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MN = 5001;

int dp[MN][MN]; //LCS를 위한 dp배열

int main() {
    int answer = 0;
    int N; cin >> N;
    string s1, s2; //원래 문자열과 뒤집은 문자열
    cin >> s1;
    s2 = s1;
    s1 = ' ' + s1;
    reverse(s2.begin(), s2.end()); //문자열 뒤집기
    s2 = ' ' + s2;
    for(int i = 1; i < s1.size(); i++) { //공통 부분 문자열 길이 구하기
        for(int j = 1; j < s2.size(); j++) {
            if(s1[i] == s2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                answer = max(answer, dp[i][j]);
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << N - dp[N][N]; //공통 부분 문자열의 길이를 원래 문자열 길이에서 뺀다. 즉 부족한 문자 개수 출력
}

 

채점 결과