C++에서 두 문자열을 동일하게 만드는 최소 비용 구하기

두 개의 문자열 A와 B와 함께 두 개의 비용 값 CostA, CostB가 주어졌다고 가정해 봅시다. 목표는 A와 B를 동일하게 만드는 데 드는 최소 비용을 찾는 것입니다. 문자열에서 문자를 삭제할 수 있으며, 문자열 A에서 삭제하는 비용은 CostA, 문자열 B에서 삭제하는 비용은 CostB입니다.

예를 들어 문자열 A = "wxyz", B = "wyzx"이고 CostA는 10, CostB는 20이라고 합시다. 이때 출력 결과는 30이 됩니다. 두 문자열에서 문자 'x'를 각각 삭제하면 A와 B가 동일해지므로 총 비용은 10 + 20 = 30입니다.

접근 방법

이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제의 변형입니다. 해결 과정은 다음과 같습니다.

1. 동적 계획법(DP)으로 A와 B의 LCS 길이를 구합니다.
2. 각 문자열의 전체 길이에서 LCS 길이를 빼면 삭제해야 할 문자의 개수를 알 수 있습니다.
3. (A에서 삭제할 문자 수 × CostA) + (B에서 삭제할 문자 수 × CostB)를 계산하면 최소 비용이 됩니다.

예제 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 두 문자열의 LCS 길이를 계산하는 함수
int lcsLength(const string& A, const string& B) {
    int m = A.length();
    int n = B.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

// 두 문자열을 동일하게 만드는 최소 비용을 계산하는 함수
int minCostToMakeIdentical(const string& A, const string& B, int costA, int costB) {
    int lcs = lcsLength(A, B);
    int deleteFromA = A.length() - lcs; // A에서 삭제할 문자 수
    int deleteFromB = B.length() - lcs; // B에서 삭제할 문자 수
    return deleteFromA * costA + deleteFromB * costB;
}

int main() {
    string A = "wxyz";
    string B = "wyzx";
    int costA = 10;
    int costB = 20;

    cout << "Minimum cost: " << minCostToMakeIdentical(A, B, costA, costB) << endl;
    return 0;
}

출력 결과

Minimum cost: 30

복잡도 분석

LCS 테이블을 채우는 데 O(m × n)의 시간 복잡도가 소요됩니다. 여기서 m과 n은 각각 문자열 A와 B의 길이입니다. 공간 복잡도 역시 DP 테이블 저장을 위해 O(m × n)이 필요하며, 두 행만 유지하도록 최적화하면 O(min(m, n))까지 줄일 수 있습니다.