[백준/python] 9251 : LCS

* LCS  = 두 수열에서 가장 긴 공통부분 수열. 즉, 연속적일 필요는 없으나 순서가 일치하는 부분 수열이어야 한다.

 

- 문제

 

- 제출

두 문자열에 대해서 Matrix를 그려 생각해보자. (문제에 예시로 나와있는 문자열을 이용함)

두 문자열을  문자를 하나 씩 추가해서 완성한다고 생각했을 때, 각 단계에 대한 LCS의 길이는 아래의 표로 정리할 수 있다.

 

	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	2	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	2	2	3	4

 

두 가지 경우로 나누어 생각해야 한다.

1. 마지막에 추가된 문자가 서로 같은 경우

     서로 같다면, 공통된 마지막 문자는 LCS에 포함되게 된다. 따라서, LCS의 길이는 두 문자열에 마지막 문자가 추가되기 전 LCS길이에 1을 더한 것임을 알 수 있다.

     => cache[i][j] += cache[i-1][j-1]+1

 

2. 다른 경우

     서로 다르다면, 공통된 마지막 문자는 LCS에 포함될 수 없다. 따라서, 두 문자열에 마지막 문자를 추가하기 전 LCS를 각각 비교하여 더 큰 값과 같아야 함을 알 수 있다. 

     => cache[i][j] += max(cache[i-1][j], cache[i][j-1])

 

import sys
firstSt = str(sys.stdin.readline().strip())
secondSt = str(sys.stdin.readline().strip())

length1 = len(firstSt)
length2 = len(secondSt)
cache = [[0]*(length2+1) for _ in range(length1+1)]

for i in range(1,length1+1):
    for j in range(1,length2+1):
        if firstSt[i-1] == secondSt[j-1]:
            cache[i][j] += cache[i-1][j-1]+1  # 두 문자열에 각 한 자리씩 추가되기 전 LCS + 1
        else:
            cache[i][j] += max(cache[i-1][j], cache[i][j-1])


print(cache[-1][-1])

 

 

처음에는 이 문제를 이해하는 것조차 힘들었다,, 도대체 LCS가 무엇인지...

그래서 사실 이 문제는 구글링을 해서 풀었다고 보면 되는;; ㅠㅠ

문제 이해를 하고 풀어냈다는 점에 만족하자^^