[BAE/<JOON> 문제풀이] 15483. 최소 편집

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

15483번: 최소 편집

서론

이 글 다 쓰고 검색해볼건데 느낌상 99프로 Well-Known 이다.

---

풀이

LCS 를 구하고 긴 문자열 길이에서 빼는 풀이를 1차적으로 떠올렸지만 문자열 앞뒤를 벗어난 경우 추가 / 제거되는 문자열 길이를 구할 수 없기 때문에 취소했다. 특히 공통 문자열이 중복되는 (aaaaaaa, aaaa) 같은 입력이 주어지는 경우 풀이가 난감해진다. 그래서 그냥 점화식을 새로 구했다.

DP[i][j] = 0 ~ i 번째 1번 문자열을 0 ~ j 번째 2번 문자열로 치환하기 위해 필요한 최소 작업 수

0번 문자열은 빈 문자열로 정의하면 모든 i, j에 대해 DP[i][0] = i 이고 DP[0][j] = j 이다.

1번 문자열 = s1

2번 문자열 = s2

s1[i] == s2[j] 인 경우

DP[i][j] = min(DP[i - 1][j] + 1, DP[i - 1][j - 1], DP[i][j - 1] + 1) 이고

아닌 경우

DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1 이다.

DP 테이블 예시

문자가 같은 경우 같은 문자를 일치시켜 작업을 하지 않을지 일치시키지 않고 작업을 할지 여부를 선택한다. 일치시키지 않는 경우가 최선인 tc는 있는지 모르겠지만 상수항 비교니까 복잡도에 영향이 없으니 그냥 넣었다.

일치시킨 경우 DP[i - 1][j - 1]이 현재의 최소 작업 수가 된다.

 

일치 시키지 않은 경우 이전 문자열 2개 ( 0 ~ (i - 1), 0 ~ (j - 1) ) 중 작은 것을 고르고 추가 작업 횟수 1을 더해준 것이 최소 작업 수가 된다. 그런데 일치하지 않는 경우에는 한가지 추가 옵션 선택이 가능하다. 바로 문자를 바꾸는 것이다. 문자를 바꾸면 현재 문자를 삭제하고 새로운 문자를 삽입하는 작업을 작업량 1로 할 수 있다. 그래서 일치하지 않는 경우에도 추가 옵션으로 DP[i - 1][j - 1] + 1이 존재 한다. 

 

정리하면 i, j 인덱스의 문자가 일치하는 경우에만 DP[i - 1][j - 1] 이라는 최적의 옵션을 선택할 수 있고

이 외 경우 이전 문자열에서 가장 적은 작업 횟수를 가진 지점을 선택해 작업을 진행해나가는 식으로 답을 구할 수 있다.

 

풀이쓰면서 보니까 LCS 아류 알고리즘 같다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
    string s1, s2; cin >> s1 >> s2;
    if (s1.size() < s2.size()) {
        auto tmp = s1; s1 = s2; s2 = tmp;
    }
    int n = s1.size(), m = s2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 2100000000));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = min({ dp[i - 1][j] + 1, dp[i - 1][j - 1], dp[i][j - 1] + 1 });
            }
            else {
                dp[i][j] = min({ dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1] }) + 1;
            }           
            //cout << dp[i][j] << " ";
        }
        //cout << "\n";
    }
    cout << dp[n][m];
    return 0;
}