BOJ 백준 9252 : LCS

시작하면서

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

BOJ 2357 - 최솟값과 최댓값

​

문제 이해

​ 해당 문제는 LCS 기본 구현을 사용하면 해결할 수 있는 문제이다. 문제에서 LCS string을 요구하지 않았기 때문에 기본 구현에서 메모리 공간을 좀 더 덜 쓰기 위해 테이블의 행을 2개만 사용했다. 테이블의 한 행을 계산하고 나면 이전에 사용한 행을 버리는 식으로 공간을 절약해서 문제를 해결했다.

​

해결

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

using namespace std;

int main()
{
    vector<vector<int> > LCSTable;
    int tableIndex = 0;
    int LCSvalue = 0;
    string A, B;

    cin >> A >> B;

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

    int iLoop = A.length() + 1;
    for (int i = 1; i < iLoop; i++)
    {
        for (int j = 1; j < LCSTable[tableIndex].size(); j++)
        {
            int iIndex = tableIndex ^ 1;

            if (A[i - 1] == B[j - 1])
            {
                LCSTable[tableIndex][j] = LCSTable[iIndex][j - 1] + 1;
            }
            else
            {
                LCSTable[tableIndex][j] = max(LCSTable[iIndex][j], LCSTable[tableIndex][j - 1]);
            }
        }
        tableIndex ^= 1;
    }

    tableIndex ^= 1;
    LCSvalue = LCSTable[tableIndex][LCSTable[tableIndex].size() - 1];

    cout << LCSvalue;

    return 0;
}