백준 9251번: LCS

[문제 링크]

9251번: LCS

---

문자열 A, B의 시작 지점에 따라 LCS는 각각 다르기 때문에 2차원 dp배열을 선언하였다.

 

문자열 A, B 모두 첫번째 원소에서 시작할 때 가지는 최대 길이는 A의 첫번째 문자와 같은 문자가 B에 존재하는 경우

A의 첫번째 문자를 LCS에 포함시킨 다음 A의 두번째 원소, B에서 A의 첫번째 문자와 일치하는 원소의 다음 위치에서 시작할 때 가지는 최대 길이 vs  첫번째 원소를 LCS에 포함시키지 않고 A의 두번째  원소, B의 첫번째 원소에서 시작할 때 가지는 최대 길이 중 더 큰 값이 정답이 된다.

 

만약 A의 첫번째 문자와 같은 문자가 B에 존재하지 않을 경우 LCS에 포함시킬 수 없기 때문에 최대 길이는 A의 두번째 원소, B의 첫번째 원소를 시작으로 할 때 최대 길이가 정답이 된다.

---

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

int memo[1000][1000];
string strA, strB;

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

int Topdown(int startA, int startB)
{
	if (startA == strA.length() || startB == strB.length())
		return 0;

	int& ret = memo[startA][startB];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = startB; i < strB.length(); i++)
		if (strA[startA] == strB[i])
			return ret = max(Topdown(startA+1, startB), Topdown(startA+1, i + 1) + 1);

	return ret = Topdown(startA+1, startB);
}

int main(void)
{
	memset(memo, -1, sizeof(memo));

	cin >> strA >> strB;

	cout << Topdown(0,0) << endl;

	return 0;
}

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