[백준][9251][C++] LCS

링크

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

9251번: LCS

해설

DP 중 Alignment 에 관한 문제이다.

 

당연히 문자열을 하나하나 다 대보면서 하면 시간제한이 걸린다.

 

백준 문제의 예시를 그대로 사용해보겠다.

ACAYKP 와 CAPCAK 인데 이걸 2차원 표로 만들어보면

위와 같은 표가 만들어지게 되는데

각 칸이 두 문자열의 해당 칸까지 만들 수 있는 LCS의 길이라고 생각하면 된다.

예를 들어 (1, 1) 의 위치는 당연히 A 와 C 만으로는 만들 수가 없으니 0이다.

그러면 (x, y) 의 LCS는 어떻게 될까?

 

우선 ( x, y ) 의 점화식을 써보면 아래와 같다.

우선 점화식대로 표를 채워보면

위와 같이 표가 만들어지게 된다.

 

그러면 왜 위와 같은 점화식이 될까?

위의 점화식은 top - down 방식인데 쉬운 이해를 위해 down - top 방식부터 생각해보겠다.

 

down - top 방식으로 생각해보면 만약 특정 (x, y) 의 값이 a 라면 그 뒤로는 어떤 문자열이 오던 최소한 a 이상일 것이다.

왜냐하면 이미 (x, y) 일 때 LCS 가 a 이므로 a값이 더 커지면 커졌지 작아지지는 않을 것이다.

그러면 이 LCS의 값이 언제 증가하는가? 바로 x 번째와 y 번째가 같을 경우에만 증가할 수 있다.

 

이제 top - down 방식으로 반대로 생각해보면 현재의 ( x, y )는 아무리 값이 작아도

( x - 1 , y ) 와 ( x , y - 1 ) 의 값 이상일 것이다. 왜냐면 down - top 방식에서 이미 증명되었기 때문이다.

그러면 LCS의 값은 왜 좌 대각선의 값에서만 +1 시키는가 하면

만약 x번째와 y번째가 같으면 LCS가 1 증가되는데 이 x번째 문자열과 y번째 문자열이 재사용되면 안 될 것이다.

바로 그렇기 때문에 좌대각의 값에서밖에 +1 을 못 시키는 것이다.

 

위의 해설이 이해가 되지 않는다면 dp alignment 에 대해 찾아보길 바란다.

해당 해설은 dp alignment 를 이미 알고 있다는 전재하에 적힌 해설이기 때문에 이해가 어려울 수 있다.

dp alignment 를 공부해보면 gap, match, mismatch 이 3가지 경우가 나오게 되는데

이 문제같은 경우 gap 과 mismatch 에 penalty 가 전혀 없는 문제라고 볼 수 있다.

 

코드

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

int table[1000][1000];
string A, B;

int max(int _a, int _b) {
	return _a > _b ? _a : _b;
}

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

	cin >> A >> B;
	
	if (A[0] == B[0])
		table[0][0] = 1;
	else
		table[0][0] = 0;

	for (int i = 1; i < A.size(); ++i)
		table[0][i] = A[i] == B[0] ? 1 : table[0][i-1];
	for (int i = 1; i < B.size(); ++i)
		table[i][0] = A[0] == B[i] ? 1 : table[i-1][0];

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

	cout << table[B.size() - 1][A.size() - 1];
	

	return 0;
}