백준 9252번 [LCS 2](C++) -yes6686- 티스토리

백준 문제 풀이: 9252 [LCS 2]

---

문제 링크: https://www.acmicpc.net/problem/9252

문제 설명:

두 문자열 A와 B가 주어졌을 때, 두 문자열의 최장 공통 부분 수열(LCS)을 구하는 문제입니다. LCS는 두 문자열에 공통으로 들어 있는 부분 수열 중 가장 긴 것을 의미합니다. 결과로 LCS의 길이와 LCS 자체를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <stack>
using namespace std;

int dp[1002][1002];
stack<char> s;

int main() {
    string a, b;
    cin >> a >> b;
    int result = -1;

    // DP 테이블 채우기
    for (int i = 0; i <= a.length(); i++) {
        for (int j = 0; j <= b.length(); j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            result = max(result, dp[i][j]);
        }
    }

    // LCS 추적
    int k = result;
    for (int i = a.length(); i > 0 && k > 0; i--) {
        for (int j = b.length(); j > 0 && k > 0; j--) {
            if (dp[i][j] == k && dp[i - 1][j - 1] == k - 1 && a[i - 1] == b[j - 1]) {
                s.push(a[i - 1]);
                k--;
                break;
            }
        }
    }

    // 결과 출력
    cout << result << '\n';
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
    cout << '\n';

    return 0;
}

예제

입력:
ACAYKP
CAPCAK

출력:
4
ACAK

---

코드 설명

• DP 테이블 채우기:
  • dp[i][j]는 문자열 A의 i번째 문자까지와 문자열 B의 j번째 문자까지 고려했을 때의 LCS 길이를 저장합니다.
  • 문자가 같으면 이전 값에서 +1을 더하고, 다르면 이전까지의 최대값을 저장합니다.
• LCS 추적:
  • DP 테이블을 역순으로 탐색하여 LCS 문자를 stack에 저장합니다.
  • 현재 dp값과 이전 dp값을 비교하면서 공통 문자를 찾습니다.

시간 복잡도

• DP 계산: O(n × m) (n과 m은 두 문자열의 길이)
• LCS 추적: O(n + m)
• 전체 시간 복잡도: O(n × m)

결과

최장 공통 부분 수열의 길이와 해당 문자열을 정확히 출력합니다.