백준 9252 / C++ / Dp

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

 

이 문제는 전형 적인 dp 문제 였다 

어느 문자를 다른 문자의 n번째 문자의 이전 문자까지의 가장 긴 LCS를 구하는 문제이다

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

int arr[1001][1001]; // 배열 크기 수정
string s1, s2;
vector<char> lcsV; // LCS 결과 문자열 저장

void lcsF() {
    int sizeOfs1 = s1.size();
    int sizeOfs2 = s2.size();

    // DP 배열 채우기
    for (int i = 1; i <= sizeOfs1; i++) {
        for (int j = 1; j <= sizeOfs2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }
            else {
                arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
            }
        }
    }

    // 역추적하여 LCS 문자열 구성
    int i = sizeOfs1, j = sizeOfs2;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcsV.push_back(s1[i - 1]);
            i--;
            j--;
        }
        else if (arr[i - 1][j] > arr[i][j - 1]) {
            i--;
        }
        else {
            j--;
        }
    }
    reverse(lcsV.begin(), lcsV.end()); // LCS 문자열을 올바른 순서로 변경
}

int main() {
    cin >> s1 >> s2;

    lcsF();

    // LCS 길이 출력
    cout << arr[s1.size()][s2.size()] << endl;

    // LCS 문자열 출력
    for (char c : lcsV) {
        cout << c;
    }
    cout << endl;

    return 0;
}