백준 9251 LCS C++

문제

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

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

입력

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

출력

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

 

풀이

2차원 배열을 이용한 다이나믹 프로그래밍(Dynamic Programing)을 이용한다.

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

알파벳을 탐색할 때 

서로 같은 알파벳인 경우 서로 이전까지의 알파벳보다 1을 더해서 저장한다. (dp[i-1][j-1] + 1)

서로 다른 알파벳인 경우 이전까지 비교했던 값 중 최댓값을 저장한다.  (dp[i-1][j] vs dp[i][j-1])

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

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}
int main() {
	//백준 9251, LCS 구하기
	//LCS(Longest common Subsequence)
	//
	string s1, s2;
	cin >> s1 >> s2;

	int l1 = s1.length();
	int l2 = s2.length();

	int dp[1001][1001];
	int i, j, ans = 0;

	//초기화
	for (i = 0; i <= l1; i++) {
		for (j = 0; j <= l2; j++) {
			dp[i][j] = 0;
		}
	}

	for (i = 1; i <= l1; i++) {
		for (j = 1; j <= l2; j++) {
			if (s1[i - 1] == s2[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[l1][l2];

	return 0;
}