LCS (feat. 백준, 9251번)

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

9251번: LCS

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9251
#include <iostream>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	int dp[1001][1001] = { 0 };
	string str1, str2;
	cin >> str1 >> str2;
	for (register int i = 1, j; i <= str1.size(); ++i)
		for (j = 1; j <= str2.size(); ++j)
			if (str1.at(i - 1) == str2.at(j - 1))		dp[i][j] = dp[i - 1][j - 1] + 1;
			else						dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
	cout << dp[str1.size()][str2.size()];
	return 0;
}
// *&)*@*

1. 해당 문제는 최장 공통 부분수열. 즉, 이어있지 않고 부분적 조합으로 서로 동일한 문자열을 찾는 방법입니다.
2. 이 문제에서 조금만 바꾸면 최장 공통 문자열. 즉, 이어진 문자열 중 서로 동일한 문자열을 찾는 방법입니다.
3. 최장 공통 문자열의 경우, else 조건을 없애고 최대값을 구하면 해답이 됩니다.

아래는 LCS. 즉, 최장 공통 부분수열과 최장 공통 문자열을 설명한 링크입니다.

이해하기 쉽게 적혀있어 추천 드립니다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence