LCS 2 (feat. 백준, 9252번)

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

9252번: LCS 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
int dp[1001][1001]{ 0 };
stack<char> ans;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	string str1, str2;
	cin >> str1 >> str2;
	register int str1_size = str1.size(), str2_size = str2.size();
	for (register int i = 0, j; i <= str1_size; ++i)
		for (j = 0; j <= str2_size; ++j)
			dp[i][j] = 0;
	for (register int i = 1, j; i <= str1_size; ++i)
		for (j = 1; j <= str2_size; ++j)
			if (str1.at(i - 1) == str2.at(j - 1))
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

	while (str1_size > 0 && str2_size > 0)
		if (dp[str1_size][str2_size] == dp[str1_size - 1][str2_size])
			--str1_size;
		else if (dp[str1_size][str2_size] == dp[str1_size][str2_size - 1])
			--str2_size;
		else
			--str1_size, --str2_size, ans.push(str1.at(str1_size));


	cout << dp[str1.size()][str2.size()] << "\n";
	while (!ans.empty())
		cout << ans.top(), ans.pop();
	return 0;
}
// *&)*@*

이전 'LCS' 문제와 동일 유형입니다.

LCS (feat. 백준, 9251번)