백준 9252번 LCS 2

백준 9252번 링크

LCS

Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다.

해당 문제에서는 결과값으로 LCS의 길이 뿐만 아니라 문자열도 요구한다. 두가지 방법이 있다.

1. 2차원 배열을 만들어 해당 칸으로 온 방향을 기록해둔다.
2. 단순하게 역추적한다.

2번 방법을 적용하여 풀었다.

코드

#include <iostream>
#include <cstring>

using namespace std;

char str1[1001];
char str2[1001];

int DP[1001][1001];

char resultStr[1001];

int main(void) {
	cin >> str1 >> str2;;

	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int idx1, idx2;

	if (str1[0] == str2[0]) {
		DP[0][0] = 1;
	}
	else {
		DP[0][0] = 0;
	}

	for (idx1 = 1; idx1 < len1; idx1++) {
		DP[idx1][0] = DP[idx1 - 1][0];

		if (str1[idx1] == str2[0]) {
			DP[idx1][0] = 1;
		}
	}

	for (idx2 = 1; idx2 < len2; idx2++) {
		DP[0][idx2] = DP[0][idx2 - 1];

		if (str2[idx2] == str1[0]) {
			DP[0][idx2] = 1;
		}
	}

	for (idx1 = 1; idx1 < len1; idx1++) {
		for (idx2 = 1; idx2 < len2; idx2++) {
			if (DP[idx1 - 1][idx2] > DP[idx1][idx2 - 1]) {
				DP[idx1][idx2] = DP[idx1 - 1][idx2];
			}
			else {
				DP[idx1][idx2] = DP[idx1][idx2 - 1];
			}

			if (str1[idx1] == str2[idx2] && DP[idx1 - 1][idx2 - 1] + 1 > DP[idx1][idx2]) {
				DP[idx1][idx2] = DP[idx1 - 1][idx2 - 1] + 1;
			}
		}
	}

	int resultLen = DP[len1 - 1][len2 - 1];

	std::cout << resultLen << endl;

	resultStr[resultLen--] = '\0';

	idx1 = len1 - 1;
	idx2 = len2 - 1;

	while (resultLen >= 0) {
		if (str1[idx1] == str2[idx2]) {
			resultStr[resultLen--] = str1[idx1];
			idx1--;
			idx2--;
		}
		else if (DP[idx1][idx2] == DP[idx1][idx2 - 1]) {
			idx2--;
		}
		else if (DP[idx1][idx2] == DP[idx1 - 1][idx2]) {
			idx1--;
		}
	}

	std::cout << resultStr << endl;

	return 0;
}