백준 9251 - LCS(C++)

문제

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 즉 LCS(Longest Common Subsequence, 최장 공통부분 수열)을 찾아라.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 최대 1000글자로 이루어져 있다.

 

예제 입력

ACAYKP
CAPCAK

 

예제 출력

4

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

이 문제를 하나하나 비교하면서 문제를 풀게 되면 제한 시간을 초과하게 된다.

 

즉, 이 문제는 중복적으로 비교하는 것이 너무 많다는 것인데 이를 해결하기 위해 다이나믹 프로그래밍을 사용해야 한다.

 

하지만 이를 어떻게 적용해야 할 지 감이 안잡히던 중 예제 답을 하나하나 만들어 보기로 했다.

 

우선 다음의 표를 보도록 하자.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

이 표는 cache 배열을 나타낸 것이고 각 표안의 값은 cache 배열 안에 들어가 있는 값을 의미한다고 생각하면 된다.

 

또한, 해당 표에 들어가는 값의 의미는, 현재 행까지의 문자열과, 현재 열까지의 문자열 사이의 LCS 길이를 의미한다.

 

그럼 각 표를 완성해 보도록 하겠다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
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

위의 표를 보면 각 표에 들어있는 값에, 해당 행까지의 문자열과, 해당 열까지의 문자열 사이의 LCS 길이를 구한 것을 알 수 있다.

 

위를 자세히 보면 규칙을 두 개 발견할 수 있다.

 

초록색은 같은 문자를 만났을 때의 규칙을 보여준다. 그리고 주황색은 다른 문자를 만났을 때의 규칙을 보여준다.

1. 같은 문자를 만났을 때 : 왼쪽 위에서 +1을 한다. 즉, cache[i][j] = cache[i - 1][j - 1] + 1 인 것을 알 수 있다.
   
   
2. 다른 문자를 만났을 때 : 왼쪽 혹은 위쪽의 값 중 더 큰 값을 가져간다. 즉, cache[i][j] = max(cache[i][j - 1], cache[i - 1][j]) 인 것을 알 수 있다.

두 개의 점화식을 통해 우리는 최종적으로 cache[str1.size()][str2.size()] 값을 얻을 수 있다.

 

코드

#include <iostream>
#include <string>

int dp[1001][1001];

int main(void)
{
	std::string A, B;
	std::cin >> A >> B;
	for (int i = 1; i <= A.size(); i++)
	{
		for (int j = 1; j <= B.size(); j++)
		{
			if (A[i - 1] == B[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	std::cout << dp[A.size()][B.size()] << std::endl;
	return 0;
}

 

문제 출처

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

9251번: LCS