#Algorithm
문제 번호
15483번(G3) 최소편집
알고리즘 + 이론
DP이고 편집횟수가 하나씩 늘어나거나 안 늘어난다는 아이디어만 가지고 있다면 거의 실버 문제보다 쉽다.
하지만 이 아이디어를 떠올려낼 수 있을까. 책에서 공부하고 그대로 풀었다. 일단 그냥 외워놔야할듯
정답 코드
# 15483번
s = list(map(str,input()))
t = list(map(str,input()))
dp = [[1000]*(len(t)+1) for _ in range(len(s)+1)]
dp[0][0] = 0
for i in range(len(s)+1):
dp[i][0] = i
for j in range(len(t)+1):
dp[0][j] = j
for i in range(1,len(s)+1):
for j in range(1,len(t)+1):
if s[i-1] == t[j-1]:
a = 0
else:
a = 1
dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+a)
print(dp[len(s)][len(t)])
느낀점 & 피드백
DP 원래 이렇게 외워서 푸는 거 맞나?
이 글이 도움이 되셨나요?