Boj 1958) Lcs 3

LCS

백준 1958

시간 복잡도

O(\(NM\))

설명

갓갓 블로그

코드

int dp[101][101][101]; // starting pos -> end_pos

int main()
{
	string A, B, C;
	cin >> A >> B >> C;

	int cur = 0;
	for (int i = 0; i < A.size(); i++)
		for (int j = 0; j < B.size(); j++)
			for (int k = 0; k < C.size(); k++)
			{
				if (A[i] == B[j] && B[j] == C[k])
					dp[i + 1][j + 1][k + 1] = dp[i][j][k] + 1;
				else
					dp[i+1][j+1][k+1] = max(dp[i][j+1][k+1], max(dp[i+1][j][k+1], dp[i+1][j+1][k]));
			}
	
	cout << dp[A.size()][B.size()][C.size()];
}