[백준 15483] 최소 편집

문제

https://www.acmicpc.net/problem/15483

 

알고리즘

DP

 

풀이

유명한 DP 문제입니다. $cache$를 다음과 같이 정의합시다

 

$cache[i][j]$ = $A$문자열의 1~$i$번째 부분 문자열과 $B$문자열의 1~$j$번째 부분 문자열이 일치하기 위한 최소 편집 거리

 

위 상태는 총 3가지 상태에서부터 갱신됨을 알 수 있습니다. 

 

$cache[i-1][j]$ 에서 $A[i]$ 문자를 삭제.

$cache[i][j-1]$ 에서 $A$에 문자를 추가.

$cache[i-1][j-1]$ 에서 $A[i]$문자를 수정.

 

이를 통해 우리는 2차원 배열을 사용해 메모이제이션을 하지만, 모든 상태 공간$O(MN)$을 필요로 하지 않음을 알 수 있습니다. 시간 복잡도는 $O(MN)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

string A, B;
int al, bl, prv, cur = 1;

int cache[2][1001];
int main() {
    FAST;
    cin >> A >> B;
    al = A.size();
    bl = B.size();
    A = " " + A;
    B = " " + B;

    for (int i = 0;i <= bl;++i) cache[0][i] = i;
    REP(i, al) {
        cache[cur][0] = i;
        REP(j, bl) {

            if (A[i] == B[j]) cache[cur][j] = cache[prv][j - 1];
            else {
                cache[cur][j] = min({ cache[prv][j],cache[cur][j - 1],cache[prv][j - 1] }) + 1;
            }

        }
        swap(prv, cur);
    }
    cout << cache[prv][bl];
    return 0;
}