9251 LCS

LCS 또한 교재에서 볼 수 있는 DP의 전형적인 문제이다.

 

 

 

길이가 각각 i, j인 문자열 x, y가 있다고 해보자.

 

LCS(i, j) 는 문자열 x, y의 최장 공통 부분 수열(LCS)이라고 할 때,

다음과 같이 점화식을 세울 수 있다.

 

LCS(i, j) =

    LCS(i-1, j-1) + 1 if x[i] == y[j]

    max( LCS(i-1, j), LCS(i, j-1) ) otherwise

 

이렇게 만들어놓고, i와 j에 따른 dynamic programming을 구현하기 위하여

d[i][j]를 만든다.

그리고 이 행렬을 잘 채워나가다가, 맨 마지막 오른쪽 부분

즉, d[i][j]가 우리가 원하는 LSC 값이다.

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int d[1001][1001];

int main() {
	string a, b;
	cin >> a >> b;

	for (int i = 1; i < a.size() + 1; i++) {
		for (int j = 1; j < b.size() + 1; j++) {
			if (a[i-1] == b[j-1]){
				d[i][j] = d[i - 1][j - 1] + 1;
			}
			else {
				d[i][j] = max(d[i - 1][j], d[i][j - 1]);
			}
		}
	}
	printf("%d\n", d[a.size()][b.size()]);
	return 0;
}