9252 LCS 2

BOJ::9252 LCS 2

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

LCS의 길이와 문자열을 찾는 문제이다.

LCS 알고리즘을(정확한 표현인지는 모르겠다) 통해 d배열을 만든 후 이를 역추적하여 문자열을 찾아냈다.

행 : ACAYKP

열 : CAPCAK

d배열의 오른쪽 아래 4에서 시작해서

1.d[i][j] == d[i-1][j] 일때

2.d[i][j] == d[i][j-1] 일때

3.d[i][j] != d[i-1][j] && d[i][j] != d[i][j-1] 일때

3가지 경우로 나누어 1이면 왼쪽으로한칸, 2이면 위쪽으로한칸, 3이면 문자열 기록+대각선으로 한칸 움직이며 문자열을 추적했다.

#include <string>
#include <iostream>
using namespace std;
 
string s1;
string s2;
int d[1001][1001];
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int main() {
    cin >> s1 >> s2;
    int n1 = s1.length();
    int n2 = s2.length();
 
    //LCS알고리즘을 통해 d배열 작성
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (s1.at(i-1) == s2.at(j-1)) {
                d[i][j] = d[i - 1][j - 1] + 1;
            }
            else {
                d[i][j] = max(d[i - 1][j], d[i][j - 1]);
            }
        }
    }
 
    cout << d[n1][n2] << endl;
 
    //문자열 추적
    int i = n1;
    int j = n2;
    string res = "";
    while (d[i][j] != 0) {
        if (d[i][j] == d[i - 1][j] ) {
            i--;
        }
        else if(d[i][j] == d[i][j-1]){
            j--;
        }
        else {
            res = s1.at(i-1) + res;
            i--;
            j--;
        }
    }
 
    cout << res << endl;
}