백준 BOJ 15483 - 최소 편집

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

15483번: 최소 편집

편집거리를 계산해내는 문제.

PHP levenstein() 함수를 써먹고싶어지는 문제다

"편집 거리" 로 표현해 두었지만,

실제로 정확한 용어는 levenshtein distance 이다.

처음 발견한 사람이 레벤슈타인 이었나 보다.

 

위키피디아에서의 레벤슈타인 거리의 정의는

아래와 같다.

해당 점화식을 해석해서 DP로 기술할수 있는 분들은 건너뛰셔도 된다.

레벤슈타인 거리는 보통 O(N^2) DP로 해결하게 되는데,

두 문자열을 A, B라고 할때

DP[i][j] : A를 i개 문자까지, B를 j개 문자까지 잘라낸 부분문자열 간의 편집거리

로 정의하게 된다.

 

당연하게도 이 정의에 따라서 정답은 DP[A.length()][B.length()]가 된다.

 

만일 A의 i번째 글자와 B의 j번째 글자가 서로 동일하다면,

아무런 편집 과정을 필요로 하지 않으므로

DP[i][j] 를 DP[i-1][j-1] 에 있는 값으로 갱신시켜주면 된다.

 

서로 동일하지 않은 경우,

모종의 편집이 들어가야 하는데

윗 위키피디아 점화식에서의 otherwise 부분과 같이

1. DP[i-1][j] + 1 으로 갱신
2. DP[i][j-1] + 1 으로 갱신
3. DP[i-1][j-1] + 1 으로 갱신

 

해주면 된다.

세가지 연산에 대해서 딱히 제한사항이 없으므로

DP[i][j]는 저 셋 중 최솟값을 가져오게 작성해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[1234][1234] = {0};

int main(){
	for(int i=0; i<1234; i++){
		dp[0][i] = i;
		dp[i][0] = i;
	}
	
	string A,B;
	cin >> A >> B;
	
	for(int i=1; i<=A.length(); i++){
		for(int j=1; j<=B.length(); j++){
			if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1];
			else dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) +1;
		}
	}
	
	cout << dp[A.length()][B.length()];
	return 0;
}