[BOJ15483] 최소 편집

[BOJ15483] 최소 편집

문제 링크

문제 설명

• 서로 다른 두 문자열을 같게 만드는데 드는 최소 연산 횟수를 구하는 문제이다.

• 문자를 삽입, 삭제, 교체 할 수 있다.(각각 연산 횟수 1)

알고리즘 설명

• A 문자열의 길이를 n, B 문자열의 길이를 m이라고 할 때, 앞에서부터 문자열을 수정하여 온다고하면, 교체되는 문자끼리 선분으로 이었을때, 전체 문자열을 놓고봤을 때 그 선분은 결코 교차하지 않는다. (최소이기 때문)

• dp[i,j] 를 A에서 i번째 문자열까지, 그리고 B에서 j번째 문자열까지의 최소 연산 횟수라고 할 수 있고, dp[i,j] 를 세가지의 경우로 나눌 수 있다. dp[i-1,j-1]에 A와 B 문자열이 1개씩 남은 경우, dp[i-1,j]에 마지막 A 문자열에 문자 한개만 남은 경우, dp[i,j-1]에 마지막 B문자열에 문자 한개만 남은 경우.

• 첫번째 경우는 문자가 각각 1개씩 남았으므로, 문자가 같은 경우 연산횟수를 추가할 필요없고, 다른 경우에는 연산횟수를 1 추가해야 한다. 두번째 경우는 A 문자열에 문자가 한개 남은 경우이므로, 삭제 연산 1을 해야 한다. 세번째 경우는 B문자열에 문자가 한개 남는 경우이므로, 삽입 연산 1을 해야한다.

• 세 경우중 가장 최소 값을 dp[i][j]에 저장하면, 최소 연산 횟수에 대해 dp 배열에 채워진다.

• dp[i][j]중 i와 j가 둘 다 0 인 경우는 dp[0][0]이 0이 될 것이고, 둘 중 하나가 0인 경우에서 dp[i][0]은 A 문자열에서 i개의 문자만큼 삭제연산을 해야되므로 i가 될 것이고, dp[0][j]는 B문자열에서 j개의 문자만큼 삽입 연산을 해야되므로 j가 될 것이다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

char A[1005], B[1005];
int dp[1005][1005];

int d(char a, char b) {
	if (a==b) return 0;
	return 1;
}

int main() {
	scanf("%s", A);
	scanf("%s", B);
	int n = strlen(A);
	int m = strlen(B);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0) dp[i][j] = j;
			else if (j == 0) dp[i][j] = i;
			else {
				dp[i][j] = min(dp[i-1][j - 1] + d(A[i-1], B[j-1]), min(dp[i-1][j] + 1, dp[i][j-1] + 1));
			}
		}
	}
	printf("%d", dp[n][m]);
	return 0;
}

코드리뷰

• 주의해야할 점은 dp배열에서 idx 1부터 문자열이 시작하므로, 그 부분에있어서 주의해야한다.

• d 함수는 문자를 비교하여 같을 경우는 연산횟수 0을 반환하고, 다를 경우는 교체를 해야되므로 연산횟수 1을 반환하는 함수이다.

---