[BOJ] 최소 편집

[BOJ] 최소 편집

Problem URL : 최소 편집

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#define MAX 1001
using namespace std;

string S1, S2;
int dp[MAX][MAX];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string tmp1, tmp2;
    cin >> tmp1 >> tmp2;

    int L1 = tmp1.size();
    int L2 = tmp2.size();

    S1 += " ";
    S1 += tmp1;
    S2 += " ";
    S2 += tmp2;
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i <= L1; i++) dp[i][0] = i;
    for (int i = 0; i <= L2; i++) dp[0][i] = i;
    for (int i = 1; i <= L1; i++) {
        for (int j = 1; j <= L2; j++) {
            //[1]
            dp[i][j] = S1[i] == S2[j] ? dp[i - 1][j - 1] : min({ dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1] }) + 1;
        }
    }
    cout << dp[L1][L2] << endl;
    return 0;
}

Comments

[1] S1[i], S2[j]이 같다면 dp[i][j]는 dp[i-1][j-1]을 그대로 쓰면 된다.
같지 않다면, dp[i-1][j-1]에서 치환을 하던가, dp[i][j-1], dp[i-1][j]에서 삽입을 하면 된다.
이 때, 삭제가 가능한 점 때문에 이전 dp에서의 삽입 방향이 상관이 없다.