[백준 C++] 9252 LCS 2 - 다이나믹프로그래밍

9252번: LCS 2

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

int DP[1001][1001];

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

	string A, B;
	cin >> A >> B;

	int N = A.size();
	int M = B.size();
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			if (A[i - 1] == B[j - 1])
			{
				DP[i][j] = DP[i - 1][j - 1] + 1;
			}
			else
			{
				DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);
			}
		}
	}

	string Solution;

	int i = N;
	int j = M;
	while (i > 0 && j > 0)
	{
		if (DP[i][j] == DP[i - 1][j])
		{
			--i;
		}
		else if (DP[i][j] == DP[i][j - 1])
		{
			--j;
		}
		else
		{
			Solution.push_back(A[i - 1]);
			--i;
			--j;
		}
	}

	cout << Solution.size() << '\n';
	for (int i = Solution.size() - 1; i >= 0; --i)
	{
		cout << Solution[i];
	}
}

---

 

DP의 메모이제이션을 활용해서 특정 두 문자열의 LCS(최장공통부분수열) 길이를 저장해서 푸는 문제입니다.

 

풀이 방법은 점화식을 이용해서 아래의 그림처럼 2차원 배열에 특정 두 문자까지의 LCS 길이를 저장해주는 것입니다.

 

i, j를 0부터 1씩 증가시키면서 두 문자를 비교하고 값을 채워줍니다.

 

두 문자가 같으면, 왼쪽 위 대각선 값에 1을 더해준 값을 저장합니다. -> DP[i][j] = DP[i - 1][j - 1] + 1

두 문자가 다르면, 왼쪽 값과 위의 값 중 더 큰 값을 저장합니다. -> DP[i][j] = max(DP[i][j - 1], DP[i - 1][j])

 

위의 과정을 반복해서 DP 값을 모두 채우고 나면 해당 배열에 저장된 값 중 가장 큰 값이 두 문자열의 LCS 길이가 됩니다.

 

 

그다음은 위의 그림처럼 DP 배열에서 맨 오른쪽 아래 칸 부터 왼쪽 또는 위쪽으로 이동하면서

현재의 값이 왼쪽 값, 위쪽 값과 모두 다르면 현재 위치의 문자를 저장합니다. - 이때는 왼쪽 위 대각선으로 이동

값이 0이 나올 때까지 반복해서 위치를 이동한 다음, 저장된 문자를 역순으로 나열하면 LCS가 됩니다.

 

---

참고자료

[백준] 9251번 C/C++ 풀이 _ LCS - Easy is Perfect

[DP] 9252번 LCS2