[백준] 15483번* (편집거리 알고리즘)

💻 C++ 기반

최소 편집
https://www.acmicpc.net/problem/15483

✔️ 편집거리 알고리즘
: 두 문자열이 얼마나 유사한지 알아보는 알고리즘

• 문자 삽입, 삭제, 변경을 최소한으로 하도록 함
• LCS의 확장판
• 개념 참고

#include <iostream>
#include <string>
#include <algorithm>

#define MAX 1001

using namespace std;

int dp[MAX][MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string A, B;
    cin >> A >> B;

    int lengthA = A.length();
    int lengthB = B.length();
    for (int i = 1; i <= lengthA; i++)
    {
        dp[i][0] = i;
    }
    for (int j = 1; j <= lengthB; j++)
    {
        dp[0][j] = j;
    }
    for (int i = 1; i <= lengthA; i++)
    {
        for (int j = 1; j <= lengthB; j++)
        {
            if (A[i - 1] == B[j - 1]) // 문자열 인덱스는 0부터 시작하므로 i - 1, j - 1로 적어줘야 함!
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
    }

    cout << dp[lengthA][lengthB];
    return 0;
}