[Baekjoon/C++] 9252번 - LCS 2

[백준] Baekjoon Online Judge

문제로 이동

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

---

풀이

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

string a, b;
int n, m;
int dp[1001][1001];

string makeLCS(int i, int j);

string makeLCS(int i, int j) {
    string s = "";

    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            s += a[i - 1];
            i--;
            j--;
        }
        else {
            if (dp[i][j] == dp[i - 1][j]) i--;
            else j--;
        }
    }

    reverse(s.begin(), s.end());

    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b;

    n = a.length();
    m = b.length();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            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]);
        }
    }

    if (dp[n][m] == 0) cout << "0\n";
    else {
        cout << dp[n][m] << '\n';
        cout << makeLCS(n, m) << '\n';
    }

    return 0;
}

 

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            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]);
        }
    }

 LCS의 길이를 구하는 부분의 코드이다. 두 문자열의 문자를 비교하여 같다면 dp[i][j]를 대각선 위치의 칸보다 1증가시키고, 아니라면 왼쪽 칸과 윗칸 중 큰 것으로 초기화한다.

 

string makeLCS(int i, int j) {
    string s = "";

    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            s += a[i - 1];
            i--;
            j--;
        }
        else {
            if (dp[i][j] == dp[i - 1][j]) i--;
            else j--;
        }
    }

    reverse(s.begin(), s.end());

    return s;
}

 LCS 문자열을 만드는 함수이다. 두 문자열의 문자가 같다면 s에 문자를 추가하고, i와 j를 -1하여 대각선으로 움직인다. 문자가 같지 않다면 현재 칸과 같은 숫자를 가진 칸으로 이동하도록 한다.

 s의 문자열은 뒤집힌 상태이므로 reverse()로 한 번 뒤집은 뒤 return 해준다.