[골드3] 15483번 : 최소 편집

🛠 문제

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

👩🏻‍💻 해결 방법

바꾸기 전 문자열을 행 크기, 바꾼 후 문자열을 열 크기로 삼은 2차원 리스트 dp를 만들어주었다
만약 행과 열에 해당하는 문자열이 같다면 왼쪽 위에 해당하는 수를 그대로 대입하고,
다르다면 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체) 중 가장 작은 값에 +1 한 값을 대입해주었다

소스 코드

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 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])

print(dp[n][m])