백준 9252 Lcs 2

문제

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

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

입력

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

출력

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

---

처음에는 vector<vector<string>> answer배열을 만들고

dp 배열을 업데이트 할 때마다 같이 값을 업데이트 해줬는데,, 시간초과가 났다. 순회하면서 string 배열을 계속 확인하는데 시간이 좀 걸리나보다;; 

 

그래서 dp배열의 역추적을 이용해 문자열을 구해보기로 하였다. 

dp 배열을 끝에서부터 확인하면서 a[i]==b[j]라면 정답 문자열에 추가하고 i와 j를 감소시킨다.

같지 않은 경우 dp[i-1][j]>= dp[i][j]라면 i만 감소시키고 , 이것도 아니라면 j를 하나 감소시켰다.

 

dp배열이 대각선으로 이동할 수 있는 경우는 현재 확인하고 있는  i, j 인덱스에서 문자가 같음을 확인한 경우고,

아니라면 왼쪽이나 위쪽으로 이동하는데 여기서 그냥 dp값이 큰 쪽으로 이동하면 된다. 

위나 아래로 이동하는데 dp값은 작아지거나 같은 경우만 있으므로 

해당 코드가 정상적으로 작동할 수 있게 된다.

 

이런 느낌으로 추적한다 

 

#include<iostream>
#include<vector>
#include <string>

using namespace std;

int main() {
	ios::sync_with_stdio(0);

	string a;
	string b;

	cin >> a;
	cin >> b;

	int s = a.size();
	int t = b.size();

	vector<vector<int>>dp(s+1,vector<int>(t+1,0));
	vector<char>answer;

	for (int i = 0; i < s; i++) {
		for (int j = 0; j < t; j++) {
			if (a[i] == b[j]) {
				dp[i+1][j+1] = dp[i][j] + 1;
			}
			else {
				if (dp[i + 1][j] > dp[i][j + 1]) {
					dp[i + 1][j + 1] = dp[i + 1][j];
				}
				else {
					dp[i + 1][j + 1] =  dp[i][j + 1];
				}
			}
		}
	}

	int i = s, j = t;
	while (i > 0 && j > 0) {
		if (a[i - 1] == b[j - 1]) {
			// 현재 문자가 일치하면 LCS에 추가하고 대각선으로 이동
			answer.push_back(a[i - 1]);
			i--;
			j--;
		}
		else if (dp[i - 1][j] >= dp[i][j - 1]) {
			// 위쪽으로 이동
			i--;
		}
		else {
			// 왼쪽으로 이동
			j--;
		}
	}

	cout << dp[s][t]<<"\n";

	for (int i = answer.size() - 1; i>= 0; i--) {
		cout << answer[i];
	}
	return 0;

}

 

어떻게 dp배열로 문자열을 찾아내는지 생각하는데 시간이 좀 걸렸다,, 연습을 좀 더 해야겠다!~