백준 9252번: LCS 2

[문제 링크]

9252번: LCS 2

---

LCS 길이를 구하는건 이전에 풀어봤던 LCS 문제들과 같았기 때문에 쉽게 구할 수 있었다.

필자는 LCS를 출력하기 위해 pair<int, string> 형태로 값을 저장했는데 시간초과가 발생하였다.

 

원인은 정확히 모르겠으나 문자열 길이를 비교하기 위해 string 문자열을 매개변수로 받는 max 함수를 호출하면서 string 복사생성자와 소멸자를 많이 호출하게 되어 그만큼 시간이 늘어난 것이라 생각한다.

 

---

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

string strA, strB, strRes;
int memo[1001][1001];

int max(int a, int b) { return a > b ? a : b; }

int Length(int hereA, int hereB)
{
	if (hereA == strA.length() || hereB == strB.length())
		return 0;

	int& ret = memo[hereA][hereB];
	if (ret != -1) return ret;

	ret = 0;

	int same = strA[hereA] == strB[hereB]; // 같으면 1 다르면 0
	ret = max(Length(hereA + 1, hereB), max(Length(hereA, hereB + 1), Length(hereA + 1, hereB + 1) + same));

	return ret;
}

void Str(int hereA, int hereB)
{
	if (hereA == strA.length() || hereB == strB.length())
		return;

	if (strA[hereA] == strB[hereB])
	{
		strRes += strA[hereA];
		Str(hereA + 1, hereB + 1);
	}
	else if (memo[hereA + 1][hereB] >= memo[hereA][hereB + 1])
		Str(hereA + 1, hereB);
	else
		Str(hereA, hereB + 1);
}


int main(void)
{
	memset(memo, -1, sizeof(memo));
	cin >> strA >> strB;

	int res = Length(0, 0);
	cout << res << endl;

	if (res != 0)
	{
		Str(0, 0);
		cout << strRes << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 98 day