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

두 개의 숫자 문자열 A와 B가 주어졌을 때, 두 문자열을 완전히 동일하게 만들기 위해 필요한 최소 비용을 구하는 문제입니다. 이때 사용할 수 있는 연산은 단 하나뿐이며, 바로 문자열에서 숫자(자릿수)를 삭제하는 것입니다. 숫자를 삭제할 때 드는 비용은 해당 숫자의 값과 같습니다.

예를 들어 A = "6789", B = "7859"라고 가정해 보겠습니다. 두 문자열을 같게 만들려면 A에서 '6'을, B에서 '5'를 삭제해야 하므로 총 비용은 6 + 5 = 11이 됩니다.

문제 접근 방식

이 문제는 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제의 변형입니다. 먼저 A와 B의 공통 부분 수열 중 자릿수 값의 합이 가장 큰 경우(lcs_cost)를 구한 뒤, 아래 공식을 적용하면 최소 비용을 계산할 수 있습니다.

최소 비용 = CostA + CostB − 2 × lcs_cost

여기서 CostA와 CostB는 각각 문자열 A와 B에 포함된 모든 자릿수의 합이며, lcs_cost는 두 문자열에 공통으로 남길 수 있는 자릿수의 합입니다. 전체 삭제 비용에서 공통 부분이 두 번 포함되는 것을 빼주는 개념이라고 이해하면 쉽습니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int longest_common_subsequence(int dp[101][101], string a, string b, int a_len,
int b_len) {
    for (int i = 0; i < 100; i++)
    for (int j = 0; j < 100; j++)
    dp[i][j] = -1;
    if (a_len < 0 || b_len < 0) {
        return 0;
    }
    if (dp[a_len][b_len] != -1)
    return dp[a_len][b_len];
    int res = 0;
    if (a[a_len] == b[b_len]) {
        res = int(a[a_len] - 48) + longest_common_subsequence(dp, a, b, a_len - 1, b_len - 1);
    } else
        res = max(longest_common_subsequence(dp, a, b, a_len - 1, b_len),
        longest_common_subsequence(dp, a, b, a_len, b_len - 1));
        dp[a_len][b_len] = res;
        return res;
}
int minCost(string str) {
    int cost = 0;
    for (int i = 0; i < str.length(); i++)
    cost += int(str[i] - 48);
    return cost;
}
int main() {
    string a, b;
    a = "6789";
    b = "7859";
    int dp[101][101];
    cout << "Minimum Cost to make these two numbers identical: " << (minCost(a) + minCost(b) - 2 * longest_common_subsequence(dp, a, b, a.length() - 1, b.length() - 1));
    return 0;
}

실행 결과

Minimum Cost to make these two numbers identical: 11