[백준] 9251번: LCS 2 (c++)

 

문제

---

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

 

9252번: LCS 2

 

문제조건

---

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

풀이

---

 

9251번: LCS

기본 LCS문제를 풀었다면 쉽게 풀 수 있는 문제이다.

LCS의 경우에는 DP를 사용하여 다음과 같이 구할 수 있다. ( 편의를 위해 0번 배열을 만들고, 0으로 초기화해놨다. )

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

C부터 한개씩 비교해보자. C를 발견하면 문자열 끝까지 비교해도 LCS의 값은 1이된다.

	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

CA의 경우는 다음과 같다. C이전에 A가 나온 경우와 C가 나오고 A가 나오는 경우를 볼 수 있다.

점화식을 만들기 위해서 한 번 더 해보자.

	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

규칙을 찾다보면 다음과 같은 점화식을 만들 수 있다.

arr[i] == arr[j] 일 때 arr[i-1][j-1] + 1
arr[i] != arr[j] 일 때 max(arr[i-1][j], arr[i][j-1])

 

	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를 찾기 위해서는 거꾸로 올라가보면 된다. 가장 끝 값(예시에서는 dp[6][6])부터 왼쪽과 위쪽을 살피며 값이 같다면 그 방향으로 옮겨주고, 더이상 이동이 불가능하다면 LCS값임을 이용해서 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

 

코드 

---

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int dp[1001][1001];

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

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

	string lcs = "";
	int col = a.length();
	int row = b.length();

	while (dp[row][col]) {

		if (dp[row][col] == dp[row - 1][col]) {
			row--;
		}
		else if (dp[row][col] == dp[row][col - 1]) {
			col--;
		}
		else {
			lcs += a[col-1];
			row--, col--;
		}

	}

	cout << lcs.length() << "\n";
	if (lcs.length() == 0) return 0;
	else {
		for (int i = lcs.length() - 1; i >= 0; i--)cout << lcs[i];
	}
}