알고리즘 :: 백준 :: DP :: 15483 :: 최소 편집

문제

문제 링크

두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.

A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.

1. 삽입: A의 한 위치에 문자 하나를 삽입한다.
2. 삭제: A의 문자 하나를 삭제한다.
3. 교체: A의 문자 하나를 다른 문자로 교체한다.

두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.

문제접근

• 일전에 다뤄본 적이 있는 유형이므로 자세한 문제 풀이 과정은 해당 포스트를 확인하자.
  https://velog.io/@embeddedjune/알고리즘-이것이-코딩-테스트다-DP-Q36-편집-거리

코드

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string lhs, rhs;
	cin >> lhs >> rhs;
	
	int lStrLen = lhs.length(), rStrLen = rhs.length();
	int dp[lStrLen + 1][rStrLen + 1];
	for (int i = 0; i <= rStrLen; ++i) dp[0][i] = i;
	for (int i = 0; i <= lStrLen; ++i) dp[i][0] = i;
	for (int y = 1; y <= lStrLen; ++y) {
		for (int x = 1; x <= rStrLen; ++x) {
			if (lhs[y - 1] == rhs[x - 1]) dp[y][x] = dp[y - 1][x - 1];
			else dp[y][x] = min(dp[y - 1][x], min(dp[y - 1][x - 1], dp[y][x - 1])) + 1;			 
		}
	}
	cout << dp[lStrLen][rStrLen] << '\n';
}

결과