[c++/백준] 9251번: LCS

문제 링크

9251번: LCS

풀이

대충 DP로 푸는 문제라는건 알았는데 알고리즘 책에서 점화식 발견

1. i랑 j는 문자열 a와 b 각각의 인덱스이다. lcs(i,j)란 a 문자열 i까지와 b 문자열 j까지를 비교해서 구한 공통 부분 수열 최댓값이다.
2. a[i]와 b[j]가 같다면 lcs(i-1, j-1) + 1이 된다.
   2-1. i나 j가 0이라면 같아도 최대 1이니까 1을 넣어줌
3. a[i]와 b[j]가 다르다면 각각 문자열에서 하나 뺀 것 중 큰 값을 골라 넣는다.
   즉, max(lcs(i-1,j), lcs(i,j-1))이 됨
   3-1. 마찬가지로 인덱스가 0이라면 0이 아닌 문자열의 lcs 값을 넣어준다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	string a, b;
	cin >> a >> b;
	
	vector<vector<int>> lcs(a.size(), vector<int>(b.size()));

	if (a[0] == b[0]) lcs[0][0] = 1;
	else lcs[0][0] = 0;

	for (int i = 0;i < a.size();i++)
	{
		for (int j = 0;j < b.size();j++)
		{
			if (i == 0 && j == 0) continue;
			if (a[i] == b[j]) {
				if (i == 0 || j==0)
				{
					lcs[i][j] = 1;
				}
				else {
					lcs[i][j] = lcs[i - 1][j - 1] + 1;
				}
			}
			else {
				if (i == 0) {
					lcs[i][j] = lcs[i][j - 1];
				}
				else if (j == 0) {
					lcs[i][j] = lcs[i - 1][j];
				}
				else {
					lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
				}
			}
		}
	}

	cout << lcs[a.size() - 1][b.size() - 1] << endl;

	return 0;
}