BOJ 9251번 LCS

BOJ : https://www.acmicpc.net/problem/9251

github : https://github.com/junho0956/Algorithm/tree/master/9251

 

LCS에 대한 설명을 포스팅해놓았습니다. 참고하시면됩니다

LCS : https://junho0956.tistory.com/39?category=868069

 

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