[BOJ] 백준 9251번 LCS

BOJ 문제 링크: https://www.acmicpc.net/problem/9251

9251번: LCS

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

두 수열을 순회하면서 두 수열중 하나가 다음 문자로 넘어가거나, 두 수열을 가르키는 문자가 서로 같으면 LCS에 추가하고 둘다 다음 문자로 넘어가는 재귀 호출을 하면서 가장 큰 값을 리턴하는 경우를 찾는다.

 

	#include<iostream>
	#include<cstring>
	using namespace std;
	string A, B;
	int cache[1000][1000];
	int lcs(int a, int b) {
	// a또는 b가 끝에 다다르면 LCS를 만들 수 없다.
	if (a == A.length() || b == B.length()) return 0;
	int& ret = cache[a][b];
	if (ret != -1) return ret;
	ret = 0;
	// A[a] == B[b]이면 해당문자를 LCS에 추가하거나
	if (A[a] == B[b])
	ret = max(ret, lcs(a + 1, b + 1) + 1);
	// B에 다음문자로 LCS를 만들거나
	ret = max(ret, lcs(a, b + 1));
	// A에 다음문자로 LCS를 만든것 중에서 제일 큰걸 리턴
	ret = max(ret, lcs(a + 1, b));
	return ret;
	}
	int main() {
	memset(cache, -1, sizeof(cache));
	cin >> A >> B;
	cout << lcs(0, 0) << endl;
	}

view raw [BOJ] 백준 9251번 LCS.cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/BOJ/blob/main/%239251.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!