문제 설명

문자열 A와 B가 주어졌을때, A를 편집해서 B로 만드려고 한다.
편집시에는 특정 위치의 문자를 삽입, 삭제, 또는 교체하는 하나의 연산을 할 수 있다. 이때 편집거리란, A를 B로 만드는데 필요한 연산의 수를 의미한다. A->B의 최소 편집거리를 구하라 ~

문제 풀이

1. 상태 정의

   $dp[i][j]$ = $str1[:i]$를 $str2[:j]$로 만드는 편집 거리

로 두었을때,

• $str1[i-1] == str2[j-1]$인 경우, dp[i][j]는 현재 보는 문자 (str1[i-1]과 str2[j-1])를 뺀 편집 거리와 같다.
• 다른 경우에는, 1+ min(삽입의 비용, 삭제의 비용, 교체의 비용)이 되는데,
  
  이렇게 그림으로 보면 이해가 쉽다.

결론적으로 점화식은,

2. 코드

import sys

input = sys.stdin.readline
str1 = input()
str2 = input()
n = len(str1)
m = len(str2)

dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    dp[i][0] = i
for i in range(1, m+1):
    dp[0][i] = i

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]) #삽입, 삭제 교체 중 최소
print(dp[n][m])

느낀점

개어렵다 진짜...... dp를 (N+1)*(M+1)인 이차원 배열로 두는 아이디어부터,,,,
삽입 삭제 교체의 비용이 왜 위와 같은지 이해를 못해서 한참 그림 그렸고,,
dp는 사실 점화식짜면 70%는 해결한 것 같은데, 처음에 점화식을 이루는 요소가 어떤 의미를 갖게 해야되는지 생각하는게 진짜 어려운듯 ㅠ

그리고 프로그래밍언어 보고서 쓸때 배운 Latex,, 대체 언제 써먹으라고 시키는건가 했는데 정답 이렇게 멋드러지게 블로깅할때 ^^!