(SWEA c++)3304. 최장 공통 부분 수열

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

SW Expert Academy

 

처음 접해보는 문제다.

DP를 이용한 방법인데, 문제의 뜻을 이해 못하여 다른 블로그를 참고하였다.

다음에 다시 공부하도록 해야겠다.

 

참고 블로그

hsp1116.tistory.com/37

최장 공통 부분 수열(Longest Common Subsequence, LCS)

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

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        string a, b, ans = "";
        vector<vector<int>> v(1001, vector<int>(1001, 0));
        cin >> a >> b;
        
        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 << "#" << tc << " " << v[a.size()][b.size()] << endl;
    }
    return 0;
}