백준 15483 최소 편집 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/15483

15483번: 최소 편집

문제

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

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

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 최소 편집 횟수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이다.

LCS처럼 2차원 dp 배열을 만드는 방식으로 풀되, 조건만 조금 다르게 하면 된다.

	0	c	a
0	0	1	2
a	1	1	1
b	2	2	2
c	3	2	3

ca, abc 두 문자열이 입력으로 주어질 때,

ca에서 세 가지 연산을 이용해 abc를 만들어야 한다.

ca를 from,

abc를 to라고 할 때,

위의 그래프를 채워보자.

예를 들어 위 그래프의 graph[2][1]는 from의 c로 to의 ab를 만드는 것을 의미한다.

이렇게 그래프를 채우면, dp의 점화식을 세울 수 있다. 

from[j] == to[i]라면 dp[i][j]= dp[i-1][j-1]

from[j] != to[i]라면 dp[i][j] = dp[i-1][j-1], dp[i-1][j], dp[i][j] 중 작은 값중 +1을 하면 된다.

코드

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

int dp[1001][1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string from, to;
	cin >> from >> to;
	int maxLen = max(from.length(), to.length());
	for (int i = 1; i <= maxLen; i++) {
		dp[0][i] = i;
		dp[i][0] = i;
	}
	for (int i = 1; i <= to.length(); i++) {
		for (int j = 1; j <= from.length(); j++) {
			if (from[j-1] == to[i-1]) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else {
				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
			}
		}
	}

	cout << dp[to.length()][from.length()];

	return 0;
}