💻 C++ 기반
✔️ 편집거리 알고리즘 응용 (참고)
1. 테이블 정의하기
dp[i][j]: str1의 i번째 문자까지의 substring과 str2의 j번째 문자까지의 substring의 차이의 최솟값
2. 점화식 찾기
str1과 str2의 각 현재 문자가 서로 같으면, dp[i - 1][j] (str1의 현재 문자 하나를 늘렸을 때), dp[i][j - 1] (str2의 현재 문자 하나를 늘렸을 때), dp[i - 1][j - 1] (str1과 str2의 문자를 늘리지 않고 그냥 비교) 중에 최솟값을 dp[i][j]에 넣어주기
str1과 str2의 각 현재 문자가 서로 다르면, 위와 똑같은 과정을 거치되 현재 문자의 알파벳 순서 차이 값을 더해줘야 함 (어떤 문자열을 얼마나 늘리던간에 상관없이 str1과 str2의 각 현재 문자끼리는 결국 반드시 비교가 되므로)
3. 초기값 정하기
str1의 첫 번째 문자를 계속 늘려가면서 str2의 문자열과 비교한 값을 dp에 넣어주기
for (int i = 1; i <= N; i++)
{
dp[i][1] = dp[i - 1][1] + abs(str1[i - 1] - str2[0]);
}
str2의 첫 번째 문자를 계속 늘려가면서 str1의 문자열과 비교한 값을 dp에 넣어주기
for (int j = 1; j <= M; j++)
{
dp[1][j] = dp[1][j - 1] + abs(str1[0] - str2[j - 1]);
}
⚠️ 문자열은 무한대로 늘릴 수 있으므로 dp 배열의 타입은 long long으로 해줄 것
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#define MAX 301
using namespace std;
long long dp[MAX][MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
string str1, str2;
cin >> str1 >> str2;
for (int i = 1; i <= N; i++)
{
dp[i][1] = dp[i - 1][1] + abs(str1[i - 1] - str2[0]);
}
for (int j = 1; j <= M; j++)
{
dp[1][j] = dp[1][j - 1] + abs(str1[0] - str2[j - 1]);
}
for (int i = 2; i <= N; i++)
{
for (int j = 2; j <= M; j++)
{
if (str1[i - 1] == str2[j - 1])
{
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
}
else
{
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + abs(str1[i - 1] - str2[j - 1]);
}
}
}
cout << dp[N][M];
return 0;
}