[BOJ]9251. LCS (python)

https://www.acmicpc.net/problem/9251

9251번: LCS

 

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 

풀이

풀이를 상세히 적기가 난해하다..
1. 핵심은 결국 이것도 DP라는 점이다. 3가지 포인트를 생각해보자.
첫째로, 큰 문제를 작은 문제로 분할해야한다. 'ACAYKP'와 'CAPCAK'의 LCS를 구하는 것은 'ACAYK'와 'CAPCA'의 LCS를 알면 구할 수 있다. (길이 5일 때의 LCS에다가 마지막 알파벳을 비교해서 같으면 1을 더해주면 된다)

두번째, 이 작은 문제들로 큰 문제를 해결할 수 있다. (앞서 언급한 것과 같다)

세번째, 이 작은 문제들이 반복해서 필요하다! 즉, 길이 2일때의 값을 알아야 3일 때를, 그 값으로 4일때, 5일때 최종적으로 6일 때 값을 구할 수 있다. 길이 6일 때의 LCS를 구하기 위해선 길이 2, 3 일 떄의 LCS 값이 반복적으로 필요하므로
이는 DP를 사용할 수 있다!!


그래서 결국 점화식을 생각해보면,
1) 새로 추가되는 알파벳이 서로 같을 경우!:
DP[i][j] = DP[i - 1][j - 1] + 1 이다. 'ACAYK', 'CAPCA'의 LCS는 'ACA'로 3이다. 이 때 만약 각각 'P'가 추가된다면
'ACAYKP' 와 'CAPCAP'의 LCS는 'ACAP'로 4가 된다.
2) 새로 추가되는 알파벳이 서로 다른 경우:
이어서, 각각 'P', 'K'가 추가되는 경우라면 'ACAYKP' 와 'CAPCAK'의 LCS는 'ACAK'로 4가 된다. 이는, 'ACAYKP'와 추가되지 않은 'CAPCA'를 비교했을 때는 LCS가 'ACA'로 3이지만, 'ACAYK' (길이5) 와 'CAPCAK'(길이6) 을 비교하면, 'ACAK'로 4가 된다. 즉, 추가되는 알파벳이 다르다면, 당연하게도 한 쪽만 추가 됐을 때의 경우 2가지 중 큰 값과 동일하게 된다.
DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]) 이다.

 

코드

 

import sys
# 공백을 추가해주어, string[0] = ' ' 이 되게 만들었다.
first_string = ' ' + sys.stdin.readline().strip()
second_string = ' ' + sys.stdin.readline().strip()

# 각 string의 길이를 저장해주고
first_len = len(first_string)
second_len = len(second_string)

# string의 길이만큼 2차원 배열을 만들었다. 이는 각 string의 길이일 때, LCS를 저장해두는 memo이다.
memo_table = [[0] * (second_len) for _ in range(first_len)]

# memo_table[i][j]는 새롭게 추가된 string이 같으면, memo[i - 1][j - 1] + 1과 같다. 그렇지 않다면, first_string이 한 개 짧을 때와 second_stirng이 한 개 짧을 때 중 큰 값을 가진다.
for i in range(1, first_len):
    first_new_str = first_string[i]
    for j in range(1, second_len):
        second_new_str = second_string[j]
        if first_new_str == second_new_str:
            memo_table[i][j] = memo_table[i - 1][j - 1] + 1
        else:
            memo_table[i][j] = max(memo_table[i][j - 1], memo_table[i - 1][j])



print(memo_table[first_len - 1][second_len - 1])