[백준] 9251-LCS(C++)

문제풀이:www.acmicpc.net/problem/9251

9251번: LCS

 

LCS알고리즘에 대한 설명은 아래 링크를 참고해주세요.

 

gusdnr69.tistory.com/192

LCS 알고리즘이란? (최장 공통 부분 수열)

 

아래는 정답코드입니다.

 LCS2, 팰린드롬 문제들도 함께 풀어보시면서 익혀보세요.

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

string a, b;
int dp[1001][1001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	string temp1, temp2;
	cin >> temp1 >> temp2;

	a = ' ' + temp1;
	b = ' ' + temp2;

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

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


	return 0;
}