[백준] 17180번* (편집거리 알고리즘 응용)

💻 C++ 기반

문자열 비교하기
https://www.acmicpc.net/problem/17180

✔️ 편집거리 알고리즘 응용 (참고)

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;
}