[백준][Python]9251번(LCS)

백준 9251번

최종 제출 코드

s = input()
e = input()

l1 = len(s)
l2 = len(e)

dp = [0]*l2

for i in range(l1):
  cnt = 0
  for j in range(l2):
    if cnt < dp[j]:
      cnt = dp[j]
    elif s[i] == e[j]:
      dp[j] = cnt+1

print(max(dp))

코드출처

◼️ 누적 DP를 활용한 문제풀이

• cnt 변수는 현재 원소의 직전 원소까지 중 가장 긴 수열의 길이를 저장하는 용도이다.
• 따라서 s[i] == e[j]일 때는 cnt 값을 업데이트 해서는 안 된다!!!
• 이때 cnt 값을 업데이트하면 문자열에 존재하는 동일한 알파벳에 대해 중복 적용되기 때문이다.
• 즉, 루프를 돌 때 이번 차례에 매치되는 원소는 나밖에 없다는 전제로 업데이트 되어야 한다.
  ex) ABC, AAAA의 경우 첫번째 원소인 A를 기준으로 dp를 업데이트할 때, s[i]==e[j]인 경우에 cnt를 업데이트하면 dp = [1, 2, 3, 4]와 같이 된다. 하지만 A는 s에 한 개 존재하기 때문에 AAAA 수열을 생성할 수 없다.
• s[i]==e[j]이면 cnt + 1한 값을 dp[j]에 저장한다.