BOJ 3793번 Common Subsequence

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

github : https://github.com/junho0956/Algorithm/blob/master/3793/3793/%EC%86%8C%EC%8A%A4.cpp

 

공통되는 최장 부분문자열인 LCS를 구하는 문제였습니다.

파일의 끝만 읽을줄 아는 방법과 LCS의 기본개념을 알고 계시면 문제를 해결할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
 
int dp[201][201];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string f, s;
 
    while (1) {
        cin >> f;
        if (cin.eof()) break;
        cin >> s;
 
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < f.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (f[i] == s[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
 
        cout << dp[f.length()][s.length()] << "\n";
    }
    
    return 0;
}