[BAEKJOON] 9251번 LCS

문 제

 

소 스  코 드

#include <iostream>
#include <string>
#include <algorithm>

int main() {
	std::string first;
	std::string second;
	
	std::cin >> first >> second;

	int **dp{ new int*[first.length() + 1] };
	for (int i = 0; i <= first.length(); ++i) {
		dp[i] = new int[second.length() + 1];
		std::fill_n(dp[i], second.length(), 0);
	}

	for (int i = 1; i <= first.length(); ++i) {
		for (int j = 1; j <= second.length(); ++j) {
			if (first[i - 1] == second[j - 1])	
            			dp[i][j] = dp[i - 1][j - 1] + 1;
			else					
            			dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	std::cout << dp[first.length()][second.length()];

	for (int i = 0; i <= first.length(); ++i) delete[] dp[i];
	delete[] dp;
	return 0;
}

 

풀 이

 

• LCS 알고리즘을 통하여 구현

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/9251