1958 LCS3

BOJ::1958 LCS3

https://www.acmicpc.net/problem/1958

세문자열의 LCS를 구하는 문제.

두문자열과 거의 비슷하지만, 3차원이므로 max비교를 몇가지 경우만 더 해주면 된다.

#include <string>
#include <iostream>
using namespace std;
 
string s1,s2,s3;
int d[101][101][101];
 
int max3(int a, int b, int c) {
    if (a > b) {
        return (a > c) ? a : c;
    }
    else {
        return (b > c) ? b : c;
    }
}
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
int main() {
    cin >> s1 >> s2 >> s3;
    int n1 = s1.length();
    int n2 = s2.length();
    int n3 = s3.length();
 
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            for (int k = 1; k <= n3; k++) {
                if (s1.at(i-1) == s2.at(j-1) && s2.at(j-1) == s3.at(k-1)) {
                    d[i][j][k] = d[i - 1][j - 1][k - 1] + 1;
                }
                else {
                    d[i][j][k] = 
                        max(
                            max3(d[i - 1][j - 1][k], 
                            d[i - 1][j][k - 1], 
                            d[i][j - 1][k - 1]),
 
                            max3(d[i - 1][j][k], 
                            d[i][j - 1][k], 
                            d[i][j][k - 1])
                    );
                }
            }
        }
    }
 
    cout << d[n1][n2][n3] << endl;
}