백준 9251번: LCS, 백준 5582번: 공통 부분 문자열

LCS, 공통 부분 문자열
 
dp는 할때마다 어려운 것 같다.
 
O(N) dp에 좀 적응했다 싶었는데 O(N²) dp가 나와서 애먹었는데,
이번엔 2차원 dp다.

이런식으로 dp를 진행하면 된다.

 

// 9251번: LCS
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < static_cast<int>(N); i++)
#define FORL(e, S) for (auto& e : S)

string s1, s2;
int dp[4001][4001];

int main() {
	cin >> s1 >> s2;
	if (s2.length() > s1.length()) swap(s1, s2);
	FOR(i, s1.length()) {
		int MAX = 0;
		FOR(j, s2.length()) {
			if (s1[i] == s2[j]) {
				MAX = max(dp[i][j] + 1, MAX);
			}
			dp[i + 1][j + 1] = max(MAX, dp[i][j + 1]);
		}
	}
	cout << dp[s1.length()][s2.length()] << endl;
}

 

// 5582번: 공통 부분 문자열

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < static_cast<int>(N); i++)
#define FORL(e, S) for (auto& e : S)

string s1, s2;
int dp[4001][4001];
int MAX = -987654321;

int main() {
	cin >> s1 >> s2;
	if (s2.length() > s1.length()) swap(s1, s2);
	FOR(i, s1.length()) {
		FOR(j, s2.length()) {
			if (s1[i] == s2[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			MAX = max(MAX, dp[i + 1][j + 1]);
		}
	}
	cout << MAX << endl;
}