백준15483번 최소 편집

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

레벤슈타인 거리를 구하는 문제이다.

어떤 문자열의 i번째가 어떤 문자열의 j번째와 다르면
그 문자열의
i - 1번째, j - 1번째 편집 횟수 + 1 (교체)
i - 1번째 j번째 편집 횟수 + 1 (삽입)
i번째 j - 1번쨰 편집 횟수 + 1 (삭제)

이고

같다면
i - 1번째 j - 1번째 편집횟수와 같음을 이용하여

이차원 배열로 DP배열을 구현하는 문제이다.

처음에는 공백으로부터 시작해서 편집을 시작하므로
또는 한글자짜리도 일관성있게 풀기 위하여 공백으로 시작해서 푼다.

공백으로부터의 편집횟수를 미리 적어놓지 않으면 이후부터는 일반성이 좀더 떨어져 첫줄에 if문을 써야한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int array[1001][1001];//레벤슈타인 거리를 저장하는 배열

int min(int x, int y, int z)
{
	if (x < y)
	{
		if (x < z) return x;
		else return z;
	}

	else//y가 x보다 작음
	{
		if (y < z) return y;
		else return z;
	}

}

int main()
{
	char string1[1001];
	char string2[1001];

	scanf("%s", string1);
	scanf("%s", string2);

	int length1 = strlen(string1);
	int length2 = strlen(string2);

	int i, j;

	for (i = 0; i <= length1; i++)
	{
		array[i][0] = i;
	}

	for (i = 0; i <= length2; i++)
	{
		array[0][i] = i;
	}

	//처음에 공백이 있다 가정하고 그 문자열을 만들기 위해 필요한 편집수 저장
	//각각 0 1 2 3 4...length

	for (i = 1; i <= length1; i++)
	{
		for (j = 1; j <= length2; j++)
		{
			if (string1[i - 1] == string2[j - 1])
			{
				array[i][j] = array[i - 1][j - 1];//글자가 같으면 그 글자는 놔두면 되므로 이전 편집수를 그대로 가져오면 됨
			}

			else
			{
				array[i][j] = min(array[i - 1][j - 1], array[i - 1][j], array[i][j - 1]) + 1;//각각 교체, 삭제, 삽입의 과정이 하나 더 들어가므로 + 1
			}
		}
	}

	printf("%d", array[length1][length2]);

	return 0;
}