악곱 == 악성곱슬

DP

---

이 문제는 편집 거리(Edit Distance)를 구하는 문제이다. 어떤 문자열 A를 B로 바꾸는데 드는 비용의 최소를 구하면 된다. 바꿀때는 3가지 연산을 사용할 수 있다.

• 추가: 임의의 위치에 문자 하나를 추가한다.
• 삭제: 임의의 문자 하나를 삭제한다.
• 교체: 임의의 문자 하나를 다른 하나로 교체한다.

이 문제를 풀면서 나는 처음에 함정에 빠졌었다. LCS를 구한 다음에 전체 길이에서 공통 길이를 빼주면 되는게 아닌가? 라고 생각했는데 어림도 없었고 그에 대한 반례는 다음과 같았다.

• A: abc, B: cde

LCS를 이용하여 풀면 답이 2가 나오는데 실제로 손으로 해보니 3이 답이었다. 따라서 뭐가 문제인지 분석을 하며 공부를 했고 아래 사진과 같은 점화식을 도출해 낼 수 있었다.

위 내용대로 구하고 가장 오른쪽 하단이 최종 결과가 된다.

이 문제에서 핵심은 점화식을 문자열 길이별로 바꾸는 최소 비용으로 두어 문자열 길이가 짧은 것을 sub problem으로 두고 푸는 것이다.

코드는 다음과 같다.

구현

---

import sys

# Minimum Edit
def solution(str_a, str_b):
    table = [[0] * (len(str_a)+1) for _ in range(len(str_b)+1)]
    table[0] = [i for i in range(len(str_a)+1)]
    for i in range(len(str_b)+1):
        table[i][0] = i
    for i in range(1, len(str_b)+1):
        for j in range(1, len(str_a)+1):
            if str_a[j-1] == str_b[i-1]:
                table[i][j] = table[i-1][j-1]
                continue
            table[i][j] = min(table[i-1][j], table[i][j-1], table[i-1][j-1]) + 1
    return table[-1][-1]

if __name__ == "__main__":
    str1 = sys.stdin.readline().rstrip()
    str2 = sys.stdin.readline().rstrip()
    print(solution(str1, str2))