BOJ 백준 9252 : LCS 2

시작하면서

　이번 문제는 최장 공통 부분 수열(LCS:Longest Common Subsequence) 문제이다.

BOJ 9252 - LCS 2

​

문제 이해

​ 해당 문제는 LCS 기본 구현을 사용하면 해결할 수 있는 문제이다. LCS에 관한 개념은 구글에 검색하면 잘 설명되어 있는 블로그가 많으니 생략한다.

​

해결

#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

string RecrusiveGetLCSstring(const vector<vector<int> >& LCSTable, const string A, const string B, int row, int col)
{
    string s = "";

    if (row == 0 || col == 0)
        return s;

    if (A[row - 1] == B[col - 1])
    {
        s += RecrusiveGetLCSstring(LCSTable, A, B, row - 1, col - 1);
    }
    else if (LCSTable[row][col - 1] > LCSTable[row - 1][col])
    {
        s += RecrusiveGetLCSstring(LCSTable, A, B, row, col - 1);
    }
    else
    {
        s += RecrusiveGetLCSstring(LCSTable, A, B, row - 1, col);
    }

    if (A[row - 1] == B[col - 1])
    {
        s += A[row - 1];
    }

    return s;
}

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

    vector<vector<int> > LCSTable;
    int LCSvalue = 0;
    string LCSstring;
    string A, B;

    cin >> A >> B;

    LCSTable.resize(A.length() + 1);
    for (int i = 0; i < LCSTable.size(); i++)
    {
        LCSTable[i].resize(B.length() + 1);
    }

    for (int i = 1; i < LCSTable.size(); i++)
    {
        for (int j = 1; j < LCSTable[i].size(); j++)
        {
            if (A[i - 1] == B[j - 1])
            {
                LCSTable[i][j] = LCSTable[i - 1][j - 1] + 1;
            }
            else
            {
                LCSTable[i][j] = max(LCSTable[i - 1][j], LCSTable[i][j - 1]);
            }
        }
    }

    LCSvalue = LCSTable[LCSTable.size() - 1][LCSTable[LCSTable.size() - 1].size() - 1];
    LCSstring = RecrusiveGetLCSstring(LCSTable, A, B, A.length(), B.length());

    if (LCSvalue != 0)
    {
		cout << LCSvalue << "\n" << LCSstring;
	}
    else
    {
        cout << LCSvalue;
    }

    return 0;
}