acmicpc_9251 (LCS)

첫 알고리즘은 백준에 있는 난이도 골드5인 LCS문제이다 문자열 길이를 구하는 문제로 알고리즘을 모르면 해매기 쉬울것 같다.

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

int dp[1001][1001];

int main() {
	string main_str, sub_str;
	cin >> main_str >> sub_str;
	main_str = "0" + main_str;
	sub_str = "0" + sub_str;
	int main_len = main_str.length();
	int sub_len = sub_str.length();

	for (int i = 1; i < main_len; ++i) {
		for (int j = 1; j < sub_len; ++j) {

			if (main_str[i] == sub_str[j]) {
				dp[i][j] = dp[i-1][j-1] + 1;//overflow방지 위해 "0"+s1, "0"+s2
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}

		}
	}

	cout << dp[main_len - 1][sub_len - 1];
}

 

주의할점은 길이만 알수 있다는 점이다! 실제 문자열은 다음 포스팅때 찾아오겠다!