(c++) BOJ 9251번: LCS

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

9251번: LCS

 

---

 

 

문제 개요

 

 

LCS(최장 공통 부분 수열) 문제는 

 

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

위를 참고해서 c++ 알고리즘으로 바꾸었다.

 

$$ LCS(X_{i},Y_{j})=\left\{\begin{matrix}
\: LCS(X_{i-1}, Y_{j-1}) +1 \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:if\: x_{i} = y_{j}\\
longest(LCS(X_{i}, Y_{j-1}), LCS(X_{i-1}, Y_{j})) \:\:\:if\: x_{i} \neq y_{j}
\end{matrix}\right. $$

 

점화식에 따라서 코드를 짜면 된다.

 

 

코드

 

 

#include <bits/stdc++.h>

using namespace std;

string a, b;
int LCS[1001][1001];
void lcs_a() {
    for (int i = 1; i <= a.size(); i++) {
        for (int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                LCS[i][j] = LCS[i-1][j-1] + 1;
            } else {
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
            }
        }
    }
}
int main(void) {
    cin >> a >> b;
    lcs_a();
    cout << LCS[a.size()][b.size()];
}