BJ9251 LCS

풀이

백트래킹 + DP

A,B 두 문자열을 받고 각각의 index를 분리해서 메모했다.

DP[indexA][indexB] : A 문자열의 indexA번째 문자부터 끝까지와 B 문자열의 indexB번째 문자부터 끝까지 중 가장 긴 LCS의 길이

라고 DP를 정의했다.

백트래킹으로 탐색하며 DP를 채워나가도록 처리했다.

1. A[idxA]와 B[idxB]가 같은지 확인한다.

   1. 같다면 초기값을 1+ (idxA+1,idxB+1)에서의 LCS
   2. 다르다면 (idxA+1,idxB) 과 (idxA,idxB+1)에서의 LCS 중 큰 값

2. 1에서 얻은 결과들 중 가장 큰 값을 현재 index에서의 LCS로 메모한다.

   idxA와 idxB가 문자열 끝까지 갔다면 0을 리턴한다.

3. 처음부터 끝까지 두개의 문자열 모두 탐색하면 최댓값을 구할 수 있다.

코드

//! 2020.03.17
// TODO BJ9251_LCS
#include<iostream>
#include<string>
using namespace std;

const int MAX = 1050;
int DP[MAX][MAX];
string A,B;

int getMax(int n1,int n2){
    if(n1>n2) return n1;
    else return n2;
}

int getResult(int idxA,int idxB){
    if(idxA>=A.size() || idxB>=B.size()) return 0;

    int& ret = DP[idxA][idxB];
    if(ret!=-1) return ret;
    if(A[idxA]==B[idxB]){
        ret = 1+getResult(idxA+1,idxB+1);
    }
    else ret = 0;
    ret = getMax(ret,getResult(idxA+1,idxB));
    ret = getMax(ret,getResult(idxA,idxB+1));
    return ret;
}

int main(){
    freopen("input.txt","r",stdin);
    getline(cin,A);
    getline(cin,B);
    for(int i=0;i<A.size();i++){
        for(int j=0;j<B.size();j++){
            DP[i][j] = -1;
        }
    }
    cout << getResult(0,0) << endl;

    return 0;
}