백준 9252번 LCS 2 C++

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

 

LCS 풀이는 검색해보면 좋은 설명들이 많이 있다.

dp배열과 추가로 문자열을 담는 배열을 만들어서 그 배열에 문자열들을 저장했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str1, str2;
	cin >> str1 >> str2;
	vector<vector<int>> dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));
	vector<vector<string>> strs(str1.length() + 1, vector<string>(str2.length() + 1, ""));
	for (int i = 1; i <= str1.length(); i++) {
		for (int j = 1; j <= str2.length(); j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				strs[i][j] = strs[i - 1][j - 1] + str1[i - 1];
			}
			else {
				if (dp[i - 1][j] > dp[i][j - 1]) {
					dp[i][j] = dp[i - 1][j];
					strs[i][j] = strs[i - 1][j];
				}
				else {
					dp[i][j] = dp[i][j - 1];
					strs[i][j] = strs[i][j - 1];
				}
			}
		}
	}
	int row = str1.length();
	int col = str2.length();
	cout << dp[row][col] << "\n" << strs[row][col];
};