[BOJ C++] 백준 5502번: 팰린드롬

 📚 문제

[BOJ C++] 백준 5502번: 팰린드롬
https://www.acmicpc.net/problem/5502

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 이 문제는 두 가지 방식으로 해결할 수 있다 .첫번째 방식은 DP를 사용하는 방법, 두번째 방식은 LCS 알고리즘을 사용하는 방법이다. (LCS도 DP를 사용하긴 하지만 ...)

 1) DP

• str[i]부터 str[j]까지 고려했을 때 추가해야하는 문자의 수를 dp[i][j]에 저장한다. dp[i][i]인 경우 str[i]부터 str[i]까지, 즉, 한 개의 문자만 고려하는 경우로 생각할 수 있으므로 추가해야할 문자는 0개이다.
• dp[i][i+1]에는 str[i]==str[i+1]이면 0, 아니면 1을 저장한다. 두 문자가 같은 경우 문자를 새로 추가하지 않아도 이미 팰린드롬을 만족하고, 다른 경우 str[i]이나 str[i+1]을 추가하면 되기 때문이다. 예를 들어, aab인 경우 다음과 같은 결과를 볼 수 있다.

 

• dp[i][j]는 세 가지 경우를 고려해야한다. dp[i+1][j]의 오른쪽에 str[i]을 추가한 경우, dp[i][j-1]의 왼쪽에 str[j]를 추가한 경우, str[i]==str[j]이므로 새로 문자열을 추가하지 않아도 되는 경우이다. 이 세 경우 중 가장 작은 값을 저장한다.
• 위 내용을 점화식으로 나타내면 다음과 같다.
  dp[i][j] = min(dp[i+1][j]+1, dp[i-1][j]+1, str[i]==str[j] ? dp[i+1][j-1] : INF)

 

• 표에서 대각선을 기준으로 왼쪽 아래 부분은 채울 필요가 없다. 2번째 문자부터 1번째 문자를 고려하는 경우와 같이 순서가 뒤집어진 경우는 고려할 필요가 없기 때문이다.

 

 2) LCS

• LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 DP를 사용하여 해결할 수 있다. 자세한 설명은 아래 링크를 참조하자.
• [이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
• [BOJ C++] 백준 9251번: LCS
• 팰린드롬은 원래 문자열과 뒤집힌 문자열의 최장 공통 부분 수열을 찾은 후, 공통으로 존재하지 않는 나머지 문자열을 추가해주는 방식으로 구할 수 있다. 예를 들어, 주어진 문자열이 "abcdefe"인 경우, 뒤집힌 문자열인 "efedcba"와 비교하여 LCS를 구한다. 이때의 LCS는 "efe"이다. LCS에 공통이 아닌 문자들을 하나씩 추가해주면 되므로 "efe"를 제외한 4개의 문자를 더 추가해주면 된다. 팰린드롬을 완성해보면 "abcdefedcba"로, 실제로도 4개의 문자를 추가하는 것이 맞다는 것을 확인할 수 있다.
• 현재 문자에서는 팰린드롬 자체가 아닌 추가해야하는 문자의 수만 구하면 되므로, 주어진 문자열의 길이에서 LCS의 길이를 빼주면 정답을 구할 수 있다.

---

 ⌨️ C++ 코드

 1) DP

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int len;
    string str;
    cin >> len >> str;
    vector<vector<int>> dp(len, vector<int>(len));

    for (int i = 0; i < len - 1; i++) {
        if (str[i] == str[i + 1])
            dp[i][i + 1] = 0;
        else
            dp[i][i + 1] = 1;
    }

    for (int j = 2; j < len; j++) {
        for (int i = 0; i < len - j; i++) {
            dp[i][i + j] = min(dp[i + 1][i + j] + 1, dp[i][i + j - 1] + 1);
            if (str[i] == str[i + j]) dp[i][i + j] = min(dp[i][i + j], dp[i + 1][i + j - 1]);
        }
    }
    cout << dp[0][len - 1];
}

 

 2) LCS

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int len;
    string str, rvs;
    cin >> len >> str;
    rvs = str;
    reverse(rvs.begin(), rvs.end());
    vector<vector<int>> dp(len + 1, vector<int>(len + 1));

    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= len; j++) {
            if (str[i - 1] == rvs[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << len - dp[len][len];
}