인프런 커뮤니티 질문&답변

#include <bits/stdc++.h>

using namespace std;

int LCSubstr(string x, string y){
    int n = x.size(), m=y.size();

    vector<vector<int>> dy(n+1,vector<int>(m+1,0));

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(x[i-1] == y[j-1])
                dy[i][j] = dy[i-1][j-1] + 1;
            else
                dy[i][j] = max(dy[i-1][j], dy[i][j-1]);
        }
    }
    
    return dy[n][m];
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int n1,n2,n3;
    string A,B;
    
    cin >> n1 >> n2 >> n3;
    cin >> A >> B;
    
    int LCSLength = LCSubstr(A, B);
    int SpaceLength = abs(int(A.size() - B.size()));
    int strLength = max(A.size(),B.size());
    
    int N1Score = LCSLength * n1; //최대공통부분 문자열 길이 * 점수
    int N2Score = SpaceLength * n2;//공백갯수 * 점수
    int N3Score = (strLength - LCSLength - SpaceLength) * n3;//(전체길이 - 공백갯수 - 최대공통부분 문자열 길이) * 점수
    
    cout << N1Score + N2Score + N3Score;
    return 0;
}