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);
}