[백준 파이썬] 9251 LCS

 

12865번: 평범한 배낭

문제

---

풀이

 

평범한 배낭과 거의 동일하게 문제를 해결하였다.
캐시 배열을 만들어 단어를 하나씩 비교하면서 LCS값을 누적시킨다.
이 때 비교하는 방법은 다음과 같다.

1. 두 알파벳이 같을경우

두 알파벳이 같을 경우에는 두 알파벳을 모두 추가하기 전의 최대값에서 +1을 하면 된다.
배열상에는 cache[i-1][j-1]과 같다.

이를 코드로 표현하면 다음과 같다.

if A[i-1] == B[j-1]:
      cache[i][j] = cache[i-1][j-1] + 1

 

2. 두 알파벳이 다를경우

두 알파벳이 다를경우 각 문자열에 문자가 추가되기 전 (i-1, j-1)의 값을 그대로 가져오면 LCS를 손해보는 일이 발생한다.

예를들어 ABC, AEB의 배열이 있을 경우 마지막 비교에서 i-1, j-1을 그대로 가져오면 LCS는 A가되어 길이는 1이 돼버린다. 이를 방지하기 위하여 i, j-1 또는 i-1, j 의 값중 큰 값을 가져오게 된다.

이 말은 즉 각 문자열에서 하나씩만 추가시켰을 때의 LCS값을 비교한 뒤 최대값을 입력한다. 

else:
      cache[i][j] = max(cache[i][j-1], cache[i-1][j])

 

모든 캐시값을 누적시키면 다음과 같은 배열이 된다.

최종적인 LCS값은 배열의 마지막값인 4가 된다.

 

---

코드

A = input().strip()
B = input().strip()

h = len(A)
w = len(B)

cache = [[0] * (w+1) for _ in range(h+1)]

for i in range(1, h+1):
  for j in range(1, w+1):
    if A[i-1] == B[j-1]:
      cache[i][j] = cache[i-1][j-1] + 1
    else:
      cache[i][j] = max(cache[i][j-1], cache[i-1][j])
  
print(cache[-1][-1])