Algorithm) SWEA 3304 최장 공통 부분 수열

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOHEx66kIDFAWr&categoryId=AWBOHEx66kIDFAWr&categoryType=CODE

SW Expert Academy

최장 공통 부분 수열 문제입니다. 

lcs를 알고 있다면 쉽지만 떠올리긴 쉽지 않은 문제라고 느껴지네요

혹 모르신다면 요 글 참고하세용

https://kuk6933.tistory.com/103

Algorithm) 최장 공통 부분 수열(Longest Common Subsequence) c++

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        string a,b;
        cin>>a>>b;
        vector<vector<int>>v (1001, vector<int>(1001, 0));

        if(a.size() > b.size()) {
            swap(a,b);
        }
        for(int i=1; i<=a.size(); i++) {
            for(int j=1; j<=b.size(); j++) {
                if(a[i-1] == b[j-1]) {
                    v[i][j] = v[i-1][j-1] +1;
                } else {
                    v[i][j] = max(v[i-1][j], v[i][j-1]);
                }
            }
        }
        cout<<"#"<<test_case<<" " << v[a.size()][b.size()]<<"\n";
    }
    return 0;
}