백준 9251번 LCS(C++)

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

9251번: LCS

 

최장 공통 수열이란 

ABCDE

BCFZ E

 

두개가 있으면 BCE가 공통 수열이다. 즉 이어져있지 않아도 순서만 맞으면 된다는 뜻이다.

이 문제는 DP분류이지만 LCS알고리즘이라는 말이 따로 있을 정도라 카테코리로 분류해도 된다고 생각이 든다. 처음에는 2 x N 배열로 문제를 해결하려 했는데 사실 알고보니 두 문자열의 길이가 다를수도 있어서 될수가 없는 풀이였다. 결국 구글링해보니 2차원 배열을 N * M 선언하여 풀이하는 문제였다.

 

배열을 선언하면 다음과 같다.

DP[]	0	A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
0	0	0	0	0	0	0	0
C(1)	0
A (2)	0			X
P (3)	0
C (4)	0
A (5)	0
K (6)	0

 

여기서 DP[2][3] 이라하면 위 테이블에서 X 친 부분이 될 것이다. 이 부분에 들어갈 정보는 CA와 ACA를 비교했을 때의 최장 공통 수열이 들어간다. 

 

DP[N][M] = N번째까지의 문자열1과 M번째 까지의 문자열2를 비교했을 때 최장 공통수열의 길이

 

그렇다면 어떻게 비교를 해야할까.

먼저 가장 윗줄을 채워보자. 

DP[1][1] = C와 A의 비교이다. 이 둘은 다르므로 길이는 0이다.

DP[1][2] = C와 AC의 비교이다. 여기서 C가 같다! 그러므로 1을 채운다. 

DP[1][3] = C와 ACA의 비교이다. 여기서 A는 C와 다르지만, 우리는 순서가 중요하지 연속은 상관없기 때문에 이전값을 그대로 넣는다.

DP[]	0	A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
0	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1	1
A (2)	0
P (3)	0
C (4)	0
A (5)	0
K (6)	0

 

다음으로 2행을 채워보자

DP[2][1] = CA와 A의 비교이다. A가 같으므로 1을 채운다.

DP[2][2] = CA와 AC의 비교이다. 이전값이 1이었으므로 1을 채운다.

DP[2][3] = CA와 ACA의 비교이다. 앗! 이번에는 같은 A가 만났다. 그렇다면, 이전 값 + 1일까? 아니다. DP[i - 1][j - 1] + 1이다. 왜냐하면 CA, ACA의 최장 공통 수열의 값은 C와 AC의 최장 공통 수열 + 1과 같기 때문이다. 

만약 옆 행이나 옆 열 + 1 을 한다면 만약 CA, ACAA 의 비교를 했을 때 최장 길이가 2가 아니라 또 A가 나왔다고 생각해서 3이 됐을 것이다. 

 

DP[]	0	A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
0	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1	1
A (2)	0	1	1	2	2	2	2
P (3)	0
C (4)	0
A (5)	0
K (6)	0

 

3행을 채워보면 다음과 같다.

DP[3][1] = CAP와 A의 비교이다. 여기서 우리는 지금까지 왼쪽 값을 가져오는 것 처럼 보였다. 그러나 윗 행의 값도 참조해야한다. 왜냐하면 CAP와 A의 비교는 CA와 A의 비교와 같을 수 밖에 없다. 만약 왼쪽만 참조한다면, 이 값은 0이됐을 것이다.

 

다시말해 ABC, BCA를 비교하는 연산이라고 가정하면 ABC와 BC를 비교한것과 AB와 BCA를 비교한 것 둘 중 큰값을 가져와야한다.

 

P는 시간을 빨리 돌려 DP[3][6]을 살펴보자 이전값들은 모두 1이 될 것이다.

CAP와 ACAYKP의 비교이다.  2행을 채웠을 때 같은 값을 만난것을 복기해보면 DP[i - 1][j - 1] + 1 이므로 (CA와 CACYKP의 최장 공통 수열의 길이 + 1 이므로) 3이된다.

그리고 나머지까지 모두 채워보면 다음과 같다.

DP[]	0	A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
0	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1	1
A (2)	0	1	1	2	2	2	2
P (3)	0	1	1	2	2	2	3
C (4)	0	1	2	2	2	2	3
A (5)	0	1	2	3	3	3	3
K (6)	0	1	2	3	3	4	4

 

그러므로 마지막 DP[N][M] 이 답이다.

 

이제 이를 바탕으로 점화식을 새워보자.

위의 케이스는 2개가 있었다. 두 문자열의 이번 비교 문자가 같은 경우와 다른 경우.

그리고 같을 때는 각 문자열의 이전 문자열 까지의 최장공통수열 + 1을 하였고

다를 경우에는 각 문자열의 이전값들 중 큰 값을 가져왔다.

 

if(문자열1[i] == 문자열2[j]) DP[i][j] = DP[i - 1][j - 1] + 1
else DP[i][j] = max(DP[i - 1][j] , DP[i][j - 1]

 

정답코드

 

#include <iostream>

using namespace std;

int dp[1002][1002];

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

	string str1, str2;

	cin >> str1 >> str2;

	int N = str1.size();
    int M = str2.size();

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	cout << dp[N][M] << '\n';
}