[C++] 백준 9251 : LCS

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

9251번: LCS

백준 9251번 LCS를 풀었다.

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

처음엔 모든 경우의 수를 찾으려 했는데 안될 것 같아서 고민하다가 다른 사람들의 코드를 참고했다.

 

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

두 문자열을 비교해서 같으면 dp[i][j]의 값은 좌상단의 값 + 1이다.

다르면 dp[i][j]의 값은 max(왼쪽 값, 위쪽 값)이다.

표를 읽는 방법은 연한 파랑색 1 기준으로 보면, 문자열 ACAY와 문자열 C 사이의 LCS 값이 1인 것이다.

 

표를 마저 채워보자.

0	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

dp배열에서 가장 큰 값이 두 수열의 LCS값이 된다.

 

아래는 전체 코드입니다.

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

string a;
string b;
int dp[1001][1001];

void fun_dp() {
	int LCS = 0;
	for (int i = 1; i < b.length(); i++) {
		for (int j = 1; j < a.length(); j++) {
			if (a[j] == b[i]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (LCS < dp[i][j])
					LCS = dp[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << LCS;
}

int main() {
	cin >> a >> b;
	a = "0" + a;
	b = "0" + b;

	fun_dp();

	return 0;
}