두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.
A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.
두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string lhs, rhs;
cin >> lhs >> rhs;
int lStrLen = lhs.length(), rStrLen = rhs.length();
int dp[lStrLen + 1][rStrLen + 1];
for (int i = 0; i <= rStrLen; ++i) dp[0][i] = i;
for (int i = 0; i <= lStrLen; ++i) dp[i][0] = i;
for (int y = 1; y <= lStrLen; ++y) {
for (int x = 1; x <= rStrLen; ++x) {
if (lhs[y - 1] == rhs[x - 1]) dp[y][x] = dp[y - 1][x - 1];
else dp[y][x] = min(dp[y - 1][x], min(dp[y - 1][x - 1], dp[y][x - 1])) + 1;
}
}
cout << dp[lStrLen][rStrLen] << '\n';
}