[C++] 백준 9252: LCS 2

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

 

 

LCS 1에서 발전한 문제이다!

https://dmoritle.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251-LCS

[C++] 백준 9251: LCS

안 풀어본 분들께서는 위의 포스팅을 참고해주시면 좋을 것 같다!

 

 

풀이

LCS 1과의 차이점은 LCS인 문자열을 출력해줘야 한다는 것이다.

dp배열을 다 구해둔 상태이니 역추적을 하면 될 것 같다.

 

 

for문과 while문 두 가지 방법이 있는데

필자는 개인적으로 while문으로 푸는 게 쉬워보여서 그렇게 구현했다.

 

 

dp배열을 구할 때 두 문자열이 같을경우 대각선 위에서 가져오고,

다를경우 위나 왼쪽의 값에서 참조했었다.

 

그 방식을 그대로 역으로 해주면 된다!

string ans = "";

        while(y >= 1 && x >= 1){
            if(dp[y-1][x] == dp[y][x]){
                y--;
            }else if(dp[y][x-1] == dp[y][x]){
                x--;
            }else{
                ans = str1[y] + ans;
                y--;
                x--;
            }
        }

 

 

 

전체 코드

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

int dp[1005][1005];

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

    string str1, str2;
    cin>>str1>>str2;

    str1 = " " + str1;
    str2 = " " + str2;

    int size1 = str1.size();
    int size2 = str2.size();

    for(int i = 1; i < size1; i++){
        for(int j = 1; j < size2; j++){
            if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    int myMax = -1;
    int x, y;
    for(int i = 1; i < size1; i++){
        for(int j = 1; j < size2; j++){
            if(myMax < dp[i][j]){
                myMax = dp[i][j];
                y = i;
                x = j;
            }
        }
    }

    cout<<myMax<<"\n";
    if(myMax != 0){
        string ans = "";

        while(y >= 1 && x >= 1){
            if(dp[y-1][x] == dp[y][x]){
                y--;
            }else if(dp[y][x-1] == dp[y][x]){
                x--;
            }else{
                ans = str1[y] + ans;
                y--;
                x--;
            }
        }

        cout<<ans;
    }
    
    return 0;
}