백준/DP
(c++) 백준 9252번: LCS 2
Nimgnoej
2021. 2. 24. 16:14
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
[풀이]
LCS가 여러가지인 경우에 아무거나 출력하라고 했으므로 가장 긴 LCS를 출력하도록 했다.
LCS를 구하는 것은 아래 풀이처럼 하고 string LCS[n][m]를 이용하여 첫번째 문자열의 n번째 문자까지와 두번째 문자열의 m번째 문자까지의 최장 LCS를 저장하도록 했다.
2021/02/24 - [백준/DP] - (c++)백준 9251번: LCS
(c++)백준 9251번: LCS
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAY..
nim-code.tistory.com
#include <iostream>
#include <string>
using namespace std;
string A, B;
int dp[1001][1001];
string LCS[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;
LCS[i][j] = LCS[i-1][j-1] + A[i - 1];
}
//다르면 이전에 구해둔 LCS중 가장 긴 것을 저장
else {
if (dp[i - 1][j] > dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
LCS[i][j] = LCS[i-1][j];
}
else {
dp[i][j] = dp[i][j - 1];
LCS[i][j] = LCS[i][j-1];
}
}
}
}
cout << dp[N][M] << '\n' << LCS[N][M] << '\n';
}
int main() {
cin >> A >> B;
DP();
return 0;
}