(c++) 백준 9252번: LCS 2

www.acmicpc.net/problem/9252

9252번: LCS 2

[풀이]

LCS가 여러가지인 경우에 아무거나 출력하라고 했으므로 가장 긴 LCS를 출력하도록 했다.

LCS를 구하는 것은 아래 풀이처럼 하고 string LCS[n][m]를 이용하여 첫번째 문자열의 n번째 문자까지와 두번째 문자열의 m번째 문자까지의 최장 LCS를 저장하도록 했다.

2021/02/24 - [백준/DP] - (c++)백준 9251번: LCS

(c++)백준 9251번: LCS

 

#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;
}