BOJ 백준 9252 LCS 2 풀이

사용언어

Visual studio 2019 C++

잘 되긴하는데 너무 메모리를 많이쓰는 풀이

string자체를 배열로 써서 그런거같음… 176916 KB니까 176MB 정도..?

#include <iostream>
#include <algorithm>

#define endl "\n"
using namespace std;

string A, B;
string dp[1001][1001];
string result = "";

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	init();
	cin >> A >> B;

	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= B.size(); j++) {
			if (A[i - 1] == B[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1];
				dp[i][j] += A[i - 1];
			}
			else {
				if (dp[i - 1][j].size() > dp[i][j - 1].size()) {
					dp[i][j] = dp[i - 1][j];
				}
				else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
	}

	cout << dp[A.size()][B.size()].size() << endl;
	cout << dp[A.size()][B.size()] << endl;
}

[9252 풀이]

#include <iostream>
#include <algorithm>

#define endl "\n"
using namespace std;

int dp[1001][1001];
string a, b;
string ans;

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	init();
	cin >> a >> b;

	a = '0' + a; 
	b = '0' + b;

	for (int i = 1; i < a.size(); i++) 
		for (int j = 1; j < b.size(); j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if (a[i] == b[j])
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
		}

	cout << dp[a.size() - 1][b.size() - 1] << endl;

	int Asize = a.size() - 1, Bsize = b.size() - 1;
	while (Asize * Bsize) {
		if (dp[Asize][Bsize] == dp[Asize - 1][Bsize])
			Asize--;
		else if (dp[Asize][Bsize] == dp[Asize][Bsize - 1])
			Bsize--;
		else 
			ans = a[Asize] + ans, Asize--, Bsize--;
	}

	cout << ans << endl;;
}