두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.
B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.
두 문자열 A와 B가 한 줄에 하나씩 주어집니다.
각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같습니다.
최소 편집 거리를 출력합니다.
cat
cut
1
sunday
saturday
3
# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
n = len(str1)
m = len(str2)
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * (m + 1) for _ in range(n + 1)]
# DP 테이블 초기 설정
for i in range(1, n + 1):
dp[i][0] = i
for j in range(1, m + 1):
dp[0][j] = j
# 최소 편집 거리 계산
for i in range(1, n + 1):
for j in range(1, m + 1):
# 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
# 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
return dp[n][m]
# 두 문자열을 입력 받기
str1 = input()
str2 = input()
# 최소 편집 거리 출력
print(edit_dist(str1, str2))