[백준 알고리즘/C++] 9251 LCS

 

 

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다

문제에선 문자열이 주어진다..

 

전에 풀고 적었던 글인데 설명이 여기 다 있으므로..

소 잃고 뇌 약간 고치기 (백준 9251 LCS C++)

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
string str1, str2;
int lcs[1001][1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> str1 >> str2;
 
    str1 = '0' + str1;
    str2 = '0' + str2;
 
    for (int i = 1; i < str2.length(); i++) {
        for (int j = 1; j < str1.length(); j++) {
            if (str2[i] == str1[j])
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            else
                lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
        }
    }
 
    cout << lcs[str2.length() - 1][str1.length() - 1];
}