백준 9252. LCS 2

LCS 2

 

---

Problem?

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

Input

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

Output

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력한다.

 

Solution

다음과 같은 방법을 이용했다.
/* https://kswims.tistory.com/189 */

9251번 문제 해결 코드에서 경로만 추가하면 되는 문제이다.

LCS 해결 방법을 알고 있으면 좋을 듯하다.

가정 dp : 해당 문자열까지의 lcs 길이 lcs_text : 해당 lcs text의 역순 저장

Code

#include	<iostream>
#include	<vector>
#include	<algorithm>
using namespace std;

#define MAX 1001
char text1[MAX], text2[MAX];
int dp[MAX][MAX];	// max length array
vector<char> lcs_text;

int main() {
	int i = 1, j = 1;
	scanf("%s", text1 + 1);
	scanf("%s", text2 + 1);

	for (i = 1; text1[i]; i++)
		for (j = 1; text2[j]; j++)
			dp[i][j] = max({ dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (text1[i] == text2[j]) });

	int ti = i - 1, tj = j - 1;
	while (ti > 0 && tj > 0) {
		if (dp[ti][tj] == dp[ti - 1][tj])
			ti--;
		else if (dp[ti][tj] == dp[ti][tj - 1])
			tj--;
		else {
			lcs_text.push_back(text1[ti]);
			ti--; tj--;
		}
	}

	cout << dp[i - 1][j - 1] << "\n";

	for (int i = lcs_text.size() - 1; i >= 0; i--)
		cout << lcs_text[i];
	cout << "\n";

	return 0;
}

 

---

lcs를 한번 잘 이해한다면 해결되는 문제라고 생각한다.