[BOJ] 15483 최소 편집_DP

최소 편집

link

이코테 풀이

• 방식 : DP
• 두 문자열의 요소를 하나씩 비교
• 같을 경우는 그대로
• 다를 경우 삭제, 변경, 추가 중 가장 작은 것을 추가

📰code

str1,str2 = input(),input()

n,m = len(str1), len(str2)
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(n+1):
    dp[i][0]=i
for j in range(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])

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡