[SWEA] 3304 최장 공통 부분 수열

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

DP를 이용해서 풀었다.

 

dp[i][j]이란?

문자열 a,b가 있었을 때 a의 i번째와 b의 j번째까지의 최대 공통 부분수열의 길이를 저장한 것이다.

범위 조심하기!

 

 

#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;
        
        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;
}