[백준] 9252번 LCS 2

9252번: LCS 2

LCS(Longest Common Subsequence) 문제이다.

 

LCS(Longest Common Substring)과 같이

문자열 A, B에서

A[i]와 B[j]가 같을 때는

DP[i][j] = DP[i-1][j-1] + 1

이 되지만

 

A[i]와 B[j]가 다를 때는

DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1

이 된다.

 

그러면 최종적으로

DP[문자열A 끝][문자열B 끝]이

LCS의 길이가 된다.

 

LCS를 출력하는 과정은

함수를 만들어 재귀 호출로

DP[문자열A 끝][문자열B 끝]부터 역으로

현재 값이 어디에서 왔는지를 추적해주어야 한다.

 

DP[i][j]에서 A[i]와 B[j]가 같을 땐

이 문자가 LCS에 포함되므로 결과에 추가해주고

대각선 위에서 왔으므로

i-1, j-1를 추적하러 간다.

 

A[i]와 B[j]가 다를 땐

왼쪽(i, j-1) 이나 위(i-1, j) 에서 왔으므로

이 중에서 더 큰 값을 가진 곳으로 추적하러 간다.

 

i나 j가 범위를 벗어나면 빠져나온다.

 

결과에 있는 문자열은 역추적 되어있는 상태이므로

그것을 뒤집은 뒤 출력해줘야 한다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a, b, res;
int dp[1002][1002];

void LCS(int x, int y) {
	if (x == 0 || y == 0) return;
	if (a[x - 1] == b[y - 1]) {
		res += a[x - 1];
		LCS(x - 1, y - 1);
	}
	else {
		if (dp[x - 1][y] > dp[x][y - 1]) LCS(x - 1, y);
		else LCS(x, y - 1);
	}
}

int main() {
	cin >> a >> b;
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			if (a[i] == b[j]) dp[i + 1][j + 1] = dp[i][j] + 1; // 같으면 대각선 위 값 + 1
			else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); // 다르면 왼쪽이나 위에서 더 큰 값을 가져옴
		}
	}

	LCS(a.size(), b.size());
	reverse(res.begin(), res.end());

	cout << dp[a.size()][b.size()] << endl;
	if (res.size()) cout << res << endl;

	return 0;
}