[BAEKJOON] 9252번 LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

문제조건

1. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제.
2. 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

첫번째로 구해야할것은 LCS의 길이이다. 나는 완전탐색으로 두 문자열을 돌면서 dynamic progrmming 으로 lcs 2차원배열을 채워줬다.

lcs[i][j] = s1의 i인덱스까지와, s2의 j인덱스까지 LCS값

당연한 얘기지만 두 문자열의 인덱스 값이 서로 같다면 다음 lcs수를 늘려준다.

다를 경우는 s1의 i-1인덱스와 s2의 j인덱스 그리고 s1의 i인덱스와 s2의 j-1인덱스의 lcs를 비교해서 더 큰 값으로 갱신해준다.

---

다음으로는 lcs가 어떤 문자열인지 직접 출력해야한다.

처음에는 조금 막막했는데, 이때까지 나는 dp를 통해서 각 인덱스에서의 lcs값을 잘 저장해놨다는 생각과 함께 각 문자열의 제일 뒤에서부터 인덱스를 한칸씩 앞으로 댕겨오면서 공통적인 부분일때만 정답 문자열에 넣어줬다.

당연히 뒤에서부터 넣어줬으니, 출력할때는 문자열을 뒤집어서 출력해야 한다는 사실을 잊지말자!

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1001

using namespace std;

int lcs[MAX][MAX];
string s1, s2;
int main(){
	cin >> s1 >> s2;
	int x = s1.length();
	int y = s2.length();
	for (int i = 1; i <= s1.length(); i++) {
		for (int j = 1; j <= s2.length(); j++) {
			if (s1[i - 1] == s2[j - 1]) lcs[i][j] = lcs[i - 1][j - 1] + 1;
			else lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
		}
	}
	cout << lcs[x][y] << '\n'; 
	string res;
	while (lcs[x][y] != 0) {
		if (lcs[x][y] == lcs[x - 1][y]) x--;
		else if (lcs[x][y] == lcs[x][y - 1]) y--;
		else {
			res += s1[x - 1];
			x--;
			y--;
		}
	}
	reverse(res.begin(), res.end());
	cout << res;
}