[백준] #문제: DP / 골드1

문제 링크 : https://www.acmicpc.net/problem/1230

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

"""
goal) 문자열 O -> 문자열 L과 같게 만들기 위해 사용하는 최소 삽입 횟수 구하기
tc2 : 
[[0, 1, 2, 3, 4], [], [0, 1, 2, 3, 4], [], [0, 1, 2, 3, 4], [], [0, 1, 2, 3, 4], [], [0, 1, 2, 3, 4], [5]]
tc3 : 범위내 인덱스 숫자가 빠진 경우 -> 사용 불가
[[], [1], [2], [3], [4], [5], [], [6]] 
testcase4 : 빈 리스트 덩어리 = 삽입한 문자
[[0], [1], [2], [], [3], [4], [], [], [5], [6], [7], [8], [9], [10], [11], [12], [], [], [], [], [13], [14], [15], [16], [], [17], [18]]
# DP
- 점화식

(1)  
d[i][j] = min(de[i][j] , dn[i][j])
- de : O[i] == L[j] 일치하는 경우 편집 거리
- dn : o[i] != L[j] 일치하지 않는 경우 

(2) 
de[i][j] = min(dn[i-1][j-1] , de[i-1][j-1]) 
#O[i] == L[j] 
[1] 바로 직전(O[:i-1]!= L[:j-1])에 일치하지 않은 상태 -> 일치 : dn[i-1][j-1]
[2] 바로 직전도 일치한 상태 : de[i-1][j-1]

[3] O[i] !=L[j] 인 경우 -> -1 

(3)
dn[i][j] = min(de[i][j-1] +1  , dn[i][j-1])
일치 O => L[j] 삽입 필요
"""

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

참고자료

https://sdev.tistory.com/entry/백준-1230-문자열-거리

🚩제출한 코드

import sys
input = sys.stdin.readline
# 0. 입력 변수 정의 및 초기화 하기
o = list(input())
l = list(input())
INF = 1000
if len(l) < len(o) :
  print(-1)
  exit()
#1. dp 정의
# dp[i][j][0] : de[i][j]로 O[:i] == L[:j]
dp = [[[0,0] for j in range(len(l)+1)] for i in range(len(o)+1)]
# 초기화
dp[0][0] = [0,INF]
for j in range(1,len(l)+1):
  dp[0][j][1] = 1 
  dp[0][j][0] = INF 
# for i in range(len(o)+1):
#   dp[i][0][0] = -1 

# #2. 점화식 
for i in range(len(o)) :
  for j in range(i+1):
    dp[i+1][j][0] = dp[i+1][j][1] = INF
  for j in range(i, len(l)):
    if o[i] == l[j] :
      dp[i+1][j+1][0] = min(dp[i][j][0] , dp[i][j][1])
    else : 
      dp[i+1][j+1][0] = INF 
    dp[i+1][j+1][1] = min(dp[i+1][j][0] +1 , dp[i+1][j][1])
#3. 출력
if min(dp[-1][-1][0],dp[-1][-1][1]) >= INF : 
  print(-1)
else :
  print(min(dp[-1][-1][0] , dp[-1][-1][1]))

🚩결과