[백준 9252] LCS 2 (C++)

https://www.acmicpc.net/problem/9252

9252번: LCS 2

문제

---

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

---

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

---

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

문제 풀이

---

dp 유형의 웰노운 문제.

문자열의 길이를 구하는 dp 배열을 생성한다. 인덱스 오류가 나지 않도록 문자열의 길이에 1을 더한 값을 배열의 행과 열의 크기로 설정한다. 두번째 문자열의 i번째 문자까지와 첫번째 문자열의 j번째 문자까지 가질 수 있는 최대 길이를 저장한다.

 

LCS를 출력하는 경우 dp[두번째 문자열의 길이][첫번째 문자열의 길이]에서부터 역으로 탐색한다.  두번째 문자열의 i번째 문자와 첫번째 문자열의 j번째 문자(두 문자)가 같지 않을 경우는 max(dp[i][j-1], dp[i-1][j])로 표현되고, 같다면 dp[i - 1][j - 1] + 1으로 표현되는데, 이를 이용한다.

만약 dp[i][j]가 dp[i-1][j]와 같다면 두 문자가 같지 않고 [i-1][j]가 [i][j-1]보다 컸다는 뜻이다. 따라서 i를 1감소시켜 해당 위치를 탐색하게 한다. 만약 dp[i][j]가 [i][j-1]과 같다면 두 문자가 같지 않고 [i][j-1]가 [i-1][j]보다 컸다는 뜻이므로 j를 1 감소시켜 해당 위치를 탐색한다.

그 두가지에 속하지 않는다면 두번째 문자열의 i번째 문자와 첫번째 문자열의 j번째 문자가 같다는 뜻이므로, 스택에 저장하고 i와 j 둘다 1씩 감소시켜 dp[i-1][j-1]을 탐색하게 한다.

배열은 행과 열이 1부터 채워지므로 둘 중 하나가 0이라면 탐색이 끝났다는 뜻이 된다.

 

아래는 코드.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str1, str2;
	cin >> str1 >> str2;
	int length1 = str1.length();
	int length2 = str2.length();
	int** dp = new int* [length2+1];
	stack<char> s;
	for (int i = 0; i < length2+1; i++)
	{
		dp[i] = new int[length1+1];
		for (int j = 0; j < length1+1; j++)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i < length2+1; i++)
	{
		for (int j = 1; j < length1+1; j++)
		{
			if (str2.at(i-1) == str1.at(j-1))
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
			}
		}
	}
	int i = length2;
	int j = length1;
	while (i >= 1 && j >= 1)
	{
		if (dp[i][j] == dp[i - 1][j])
		{
			i--;
		}
		else if (dp[i][j] == dp[i][j - 1])
		{
			j--;
		}
		else
		{
			s.push(str2.at(i-1));
			i--;
			j--;
		}
	}
	cout << dp[length2][length1] << "\n";
	while (!s.empty())
	{
		cout << s.top();
		s.pop();
	}
	return 0;
}