1958번: LCS 3

📝 Memo

Memory : 6044 KB

Time : 4 ms

🖥️ Code

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

int max3(int a, int b, int c)
{
	if (a >= b && a >= c)
		return a;
	if (b >= a && b >= c)
		return b;
	return c;
}

int dp[101][101][101];
int main(){
	string s1, s2, s3;
	cin >> s1 >> s2 >> s3;
	s1 = "1"+s1;
	s2 = "2"+s2;
	s3 = "3"+s3;

	int n1,n2,n3;
	int result = 0;
	n1 = s1.length();
	n2 = s2.length();
	n3 = s3.length();
	memset(dp,0,sizeof(dp));
	for(int i=1;i<n1;i++){
		for(int j=1;j<n2;j++){
			for(int k=1;k<n3;k++){
				dp[i][j][k] = max3(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1]);
				if(s1[i] == s2[j] && s1[i] == s3[k]){
					dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
					if(result < dp[i][j][k]){
						result = dp[i][j][k];
					}
				}
			}
		}
	}
	printf("%d",result);
}