[알고리즘] 백준 9252번: LCS 2 (C++)

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

9252번: LCS 2

저번에 공부했던 LCS알고리즘을 이해하고 있다면 똑같은 DP의 방식으로 문자열 배열 DP를 돌리면 된다.

(LCS 정리 https://draw-code-boy.tistory.com/126)

 

[AC 코드]

cache2 == 문자열 메모이제이션 배열

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#define MAX 1000 + 1
#define ll long long
using namespace std;

int cache[MAX][MAX];
string cache2[MAX][MAX];

string strMax(string n1, string n2) {
	if (n1.length() > n2.length()) {
		return n1;
	}
	else {
		return n2;
	}
}

int main() {
	string a, b;
	cin >> a >> b;
	a = ' ' + a;
	b = ' ' + b;
	for (int i = 1; i < a.size(); i++) {
		for (int j = 1; j < b.size(); j++) {
			if (a[i] == b[j]) {
				cache[i][j] = cache[i - 1][j - 1] + 1;
				cache2[i][j] = cache2[i - 1][j - 1] + a[i]; // a[i]랑 b[j]가 같아서 둘 중 아무거나 넣음
			}
			else {
				cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
				cache2[i][j] = strMax(cache2[i - 1][j], cache2[i][j - 1]);
			}
		}
	}

	cout << cache[a.size() - 1][b.size() - 1] << '\n';
	cout << cache2[a.size() - 1][b.size() - 1];
	return 0;
}

---

+2022.03.11 메모리 초과로 인한 다시 풀기

아무래도 두 개의 cache 2차원 배열을 사용해서 메모리 초과가 나온 듯 하다.

큐와 역추적을 활용해 다시 풀어주었다.

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#define MAX 1000 + 1
#define ll long long
using namespace std;

int cache[MAX][MAX];
queue<char> s;
string a, b;

void sol(int row, int col){
    if(cache[row][col] == 0) return;
    if(a[row] == b[col]){
        sol(row - 1, col - 1);
        s.push(a[row]);
    }
    else{
        cache[row - 1][col] > cache[row][col - 1] 
        ? sol(row - 1, col) : sol(row, col - 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	cin >> a >> b;
	a = ' ' + a;
	b = ' ' + b;
	for (int i = 1; i < a.size(); i++) {
		for (int j = 1; j < b.size(); j++) {
			if (a[i] == b[j]) {
				cache[i][j] = cache[i - 1][j - 1] + 1; // a[i]랑 b[j]가 같아서 둘 중 아무거나 넣음
			}
			else {
				cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]);
			}
		}
	}
    
    
	cout << cache[a.size() - 1][b.size() - 1] << '\n';
	sol(a.size() - 1, b.size() - 1);
	while(!s.empty()){
	    cout << s.front();
	    s.pop();
	}
	return 0;
}