[알고리즘] LCS (백준 9251)

9251 LCS
그림으로 알아보는 LCS

LCS : 최장공통부분수열

최장공통부분수열을 구하는 알고리즘은 다음과 같다.

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

풀이

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
string a, b;

int LCS[1001][1001];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>a>>b;
    int ret = 0;
    for(int i=0;i<=a.size();i++){
        for(int j=0;j<=b.size();j++){
            if(i == 0 || j == 0) LCS[i][j] = 0;
            else if(a[i-1] == b[j-1]) LCS[i][j] = LCS[i-1][j-1]+1;
            else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
            ret = max(ret,LCS[i][j]);
        }
    }
    cout<<ret;
}