Boj 9252) Lcs 2

LCS

백준 9252

설명

갓갓 블로그

시간 복잡도

O(\(NM\))

코드

int dp[1001][1001]; // starting pos -> end_pos

int main()
{
	string inputA, inputB;
	cin >> inputA >> inputB;

	int cur = 0;
	for (int i = 0; i < inputA.size(); i++)
	{
		for (int j = 0; j < inputB.size(); j++)
		{
			if (inputA[i] == inputB[j])
				dp[i + 1][j + 1] = dp[i][j] + 1;
			else 
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	
	cout << dp[inputA.size()][inputB.size()] << endl;
	
	int x = inputA.size(), y = inputB.size();
	stack<char> ans;
	while (dp[x][y])
	{
		if (dp[x][y] == dp[x - 1][y]) x--;
		else if (dp[x][y] == dp[x][y - 1]) y--;
		else {
			ans.push(inputA[x-1]);
			x--; y--;
		}
	}
	while (!ans.empty())
	{
		cout << ans.top();
	    ans.pop();
	}
}

/*
	ACAYKP / CAPCAK

	if(A[i] == B[j])
		[i,j] = [i-1,j-1]+1
	else [i,j] = max([i-1,j], [i, j-1])
	
	  - A C A Y K P
	C 0 0 1 1 1 1 1
	A 0 1 1 2 2 2 2
	P 0 1 1 2 2 2 3
	C 0 1 2 2 2 2 3
	A 0 1 2 3 3 3 3
	K 0 1 2 3 3 4 4

*/