백준 9252 C++ - LCS 2

필자:

 

LCS의 정의를 이해하는데 시간이 걸렸다. 공부해보니 순서대로 각 두 문자열의 가장 긴 공통요소를 구하는 뜻이다.

또한 문제 유형이 DP인걸 이해하는데도 시간이 걸렸다.

 

 

[핵심 사고 ]

문자가 같으면 DP[i][j]= DP[i-1][j-1] +1  왼쪽 위에서 하나 더해준다.
문자가 다르면 DP[i][j] = max(DP[i-1][j], DP[i][j-1])   왼쪽 혹은 위쪽중 큰 값을 저장한다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
using namespace std;

int N;
int D[1001][1001];
string A, B;
vector<char> Path;
void getText(int r, int c);

int main(void) {
	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]) {
				D[i][j] = D[i - 1][j - 1] + 1;
			}
			else {
				D[i][j] = max(D[i - 1][j], D[i][j - 1]);
			}
		}
	}
	cout << D[A.size()][B.size()];
	cout << '\n';
	getText(A.size(), B.size());
	for (int i = Path.size() - 1; i >= 0; i--) {
		cout << Path[i];
	}

	cout << '\n';
}

void getText(int r, int c) {
	if (r == 0 || c == 0)return;

	if (A[r - 1] == B[c - 1]) {
		Path.push_back(A[r - 1]);
		getText(r - 1, c - 1);
	}
	else {
		if (D[r - 1][c] > D[r][c - 1]) {
			getText(r - 1, c);
		}
		else getText(r, c - 1);
	}
}