BaekJoon(9251)::LCS

문제

9251번: LCS

문제파악

해당문제는 단순하게 제목에서부터 풀이법을 말해주고있다.

Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)

개인적으로 정리해두 해당글을 참조하면 될 듯하다.

문제풀이

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

int dp[1001][1001] = { 0, };
int max_lengh = 0;

int max(int num1, int num2) {
	return num1 > num2 ? num1 : num2;
}

int main() {
	string str1;
	string str2;

	cin >> str1 >> str2;

	for (int i = 0;i <= str1.length();i++) {
		
		for (int j = 0; j <= str2.length(); j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 0;
			}
			else if (str1[i-1] == str2[j-1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}

			max_lengh = max(max_lengh, dp[i][j]);
		}
	}
	cout << max_lengh << endl;

	return 0;
}