백준/DP
(c++)백준 9251번: LCS
Nimgnoej
2021. 2. 24. 16:13
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
[풀이]
dp[i][j] = A문자열의 i번째까지, B문자열의 j번째까지 가장 긴 부분 수열의 길이
#include <iostream>
#include <algorithm>//max
#include <string>
using namespace std;
string A, B;
int dp[1001][1001];
void DP() {
int N = A.size();
int M = B.size();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[N][M] << '\n';
}
int main() {
cin >> A >> B;
DP();
return 0;
}