백준 15483번 최소 편집

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

15483번: 최소 편집

memo[a][b]를 A를 앞에서 a만큼 자르고 B를 앞에서 b만큼 자른 두 문자열을 같게 만드는데 필요한 최소 편집 횟수로 잡았다.

 

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

int memo[1001][1001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	string A, B;
	cin >> A >> B;

	for (int i = 0; i <= A.size(); i++){
		for (int j = 0; j <= B.size(); j++){
			int a = 1000;
			if (!i && !j) a = 0;//두 문자열이 없으니 같다
			else if (!i || !j) a = i + j;//A 또는 B를 없어질때까지 문자 삭제
			if (i && j){
				if (memo[i - 1][j - 1] < a) a = memo[i - 1][j - 1];
				if (A[i - 1] != B[j - 1]) a++;//A의 i번째와 B의 j번째가 다르면 두 문자열중 하나의 마지막 문자를 다른 문자열의 마지막 문자로 변경
			}
            //두 문자열중 하나의 마지막 문자를 제거하거나 다른 문자열의 뒤에 삽입하는 경우
			if (i) if (memo[i - 1][j] + 1 < a) a = memo[i - 1][j] + 1;
			if (j) if (memo[i][j - 1] + 1 < a) a = memo[i][j - 1] + 1;
			memo[i][j] = a;
		}
	}

	cout << memo[A.size()][B.size()];

	return 0;
}