문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

---

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

---

출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

문제 링크

풀이

참고 블로그

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string line1;
string line2;
vector table(1001, vector<int>(1001, 0));

int main(){

    getline(cin, line1);
    getline(cin, line2);
    line1.insert(0, " ");
    line2.insert(0, " ");
    
    // 0을 참고해야 하기 때문에 0라인은 비워둡니다.
    for (int i=0; i < line1.size(); i++){
        for(int j=0; j<line2.size(); j++){
            if ( i == 0 || j == 0 ) continue;

            if ( line1[i] == line2[j] ) {
                table[i][j]  = table[i-1][j-1] + 1;
            }
            else{
                table[i][j] = max(table[i-1][j], table[i][j-1]);
            }
        }
    }
    cout << table[line1.size()-1][line2.size()-1] << endl;
    return 0;
}