[ 백준 9252 ] LCS2 (C++)

백준의 LCS2(9252) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1. 문제를 풀기전에, 혹시나 LCS (9251번 문제)를 풀어보지 않았다면, 풀어보고 오길 바란다. 문제가 연관되는 부분이 있고, 공통적

   으로 구해야 하는 부분이 있기 때문에, 이 글에서는 LCS와 공통된 부분에 대한 설명은 생략하고, LCS2에서 구해야 되는 부분에

   대해서만 설명을 할 것이다.

   [ LCS(9251번 문제) 바로가기 ]

   [ LCS(9251번 문제) 풀이 바로가기 ]

   위의 글을 읽고 LCS를 풀고 왔다면, LCS의 길이를 출력하는 방법은 해결할 수 있을 것이다.

   이 문제에서도 똑같은 방식으로 구현해주었다.

   그렇다면, 이 글에서는 LCS의 실제 문자열이 무엇인지를 출력하는 부분을 어떻게 찾아낼지 알아보자.

   사실, LCS의 길이를 출력하는 부분에 대해서 이해를 완벽하게 했다면, 이 부분 또한 쉽게 구현할 수 있다.

   본인은, 이부분 구현을 위해서 string LCS[][]라는 2차원 배열을 사용해주었다.

   이 후, 문자열을 추가하는 방법은 최대 길이를 구하는 방법과 똑같다.

   2개의 문자열을 비교하면서, 같다면 해당 문자 추가, 그게 아니라면 더 긴 놈의 문자열을 선택 !

  

   LCS의 길이를 구하는 방법을 이해했다면 이 부분도 소스코드를 본다면 쉽게 이해할 수 있을 것이다.

[ 소스코드 ] 

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
string A, B;
int DP[MAX][MAX];
string LCS[MAX][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> A >> B;
}
 
void Solution()
{
    int A_Size = A.length();
    int B_Size = B.length();
 
    for (int i = 1; i <= A_Size; i++)
    {
        for (int j = 1; j <= B_Size; j++)
        {
            if (A[i - 1] == B[j - 1])
            {
                DP[i][j] = DP[i - 1][j - 1] + 1;
                LCS[i][j] = LCS[i][j] + LCS[i - 1][j - 1] + A[i - 1];
            }
            else
            {
                DP[i][j] = Bigger(DP[i - 1][j], DP[i][j - 1]);
                if (LCS[i - 1][j].length() > LCS[i][j - 1].length())
                {
                    LCS[i][j] = LCS[i - 1][j];
                }
                else
                {
                    LCS[i][j] = LCS[i][j - 1];
                }
            }
 
        }
    }
 
    cout << DP[A_Size][B_Size] << endl << LCS[A_Size][B_Size] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}