[BOJ/Step15] 9251 : LCS (Python)

www.acmicpc.net/problem/9251

9251번: LCS

---

어우 너무 어려웠다

문제을 백번 읽어도 대체 이걸 어떻게 풀어야하나 모르겠는.. 그런...

그래서 찾아봤는데 DP의 유명한 문제라더라 LCS..

아니나다를까 풀이 방법을 봤는데도 이해하는데 한참 걸렸다

다들 아... 이렇게 푸는구나만 설명하고 왜 이렇게 푸는지는 설명을 안해주셔가지고 너무 괴로웠다

뭐 설마 다들 풀이 방법을 보면 번쩍 하고 이유가 이해되는건가 나만 안되는건가 ㄴㅇㄱ

아무튼 머리 쥐어싸매고 이해했다

 

두개의 문자열이 있다

0으로 채워진 표를 채워나가는 방식으로 계산해보자

 

문제의 예제로 주어진 ACAYKP와 CAPCAK의 경우

각 칸에는 맨 위의 알파벳과 맨 왼쪽의 알파벳이 추가되었을 때의 LCS 길이를 적는다

즉 (4, 4)에는 AC에 A가 추가되었을 때, CA에 P가 추가되었을 때의 LCS 길이를 적을 것이다

(2, 2) : A와 C를 비교한다. 중복되는 수열이 없으므로 0

(2, 3) : AC와 C를 비교한다. C가 중복된다. 1

(2, 4) : ACA와 C를 비교한다. 이전에 이미 C가 중복되어 1이 되었으므로 1

(2, 5) : ACAY와 C를 비교한다. 이전에 이미 C가 중복되어 1이 되었으므로 1

(2, 6) : ACAYK와 C를 비교한다. 이전에 이미 C가 중복되어 1이 되었으므로 1

(2, 7) : ACAYKP와 C를 비교한다. 이전에 이미 C가 중복되어 1이 되었으므로 1

(3, 2) : A와 CA를 비교한다. A가 중복된다. 1

(3, 3) : AC와 CA를 비교한다. 이전에 이미 A가 중복되어 1이 되었므로 1. C도 중복되지만 CA와 AC는 중복되지 않기 때문에 여전히 1 

(3, 4) : ACA와 CA를 비교한다. CA가 중복된다. 2

(3, 5) : ACAY와 CA를 비교한다. 이전에 이미 CA가 중복되어 2이 되었으므로 2

(3, 6) : ACAYK와 CA를 비교한다. 이전에 이미 CA가 중복되어 2이 되었으므로 2

(3, 7) : ACAYKP와 CA를 비교한다. 이전에 이미 CA가 중복되어 2이 되었으므로 2

위 과정을 보면 노란 하이라이트 부분의 두 알파벳이 같을 때(= 맨 위의 알파벳과 맨 왼쪽의 알파벳이 같을 때)

(x-1, y-1) + 1이 되는 것을 알 수 있다. 어째서 (x-1, y-1)에 1을 더하는가?

3자리수의 S1과 4자리수의 S2에 각각 같은 알파벳이 추가되었다면

4자리수의 S1과 5자리수의 S2가 되어 3자리수의 S1과 4자리수의 S2일때의 LCS에 1이 추가되기 때문이다

 

위같은 방법을 반복하여 표를 가득 채우면 다음과 같다

엇 그런데 위 표에 (5, 7)을 보면 알파벳이 같지도 않은데 3이 되었다.

CAPC와 ACAYKP의 LCS를 구하는데 어라 CAP 3자리다.

CAP와 ACAYKP의 LCS 또한 CAP 3자리다. CAP에 C를 추가해도 변하지 않는다.

(x, y)를 구할 때 (x-1, y) 와 (x, y-1)을 비교하여 더 큰것을 가져오면 될 듯 하다.

 

이로써 우리는 (x, y) 를 구할 때

1. x = y 라면 (x-1, y-1) + 1

2. x != y 라면 max( (x-1, y), (x, y-1))

라는 것을 알아냈다!

 

# 9251.py

s1 = str(input())
s2 = str(input())

s1s2 = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            s1s2[i][j] = s1s2[i-1][j-1] + 1
        else:
            s1s2[i][j] = max(s1s2[i-1][j], s1s2[i][j-1])

print(s1s2[i][j])