[파이썬 | BOJ | 9251] LCS

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

9251번: LCS

문제

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

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

입력

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

출력

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

 

풀이

알고리즘 분류 : 다이내믹 프로그래밍

 

어디서 많이 본 문제라고 느꼈는데, 대학 강의로 수강했던 알고리즘 강의 ppt에 있는 유명한 알고리즘 문제이다.

 

두 string을 각각 한 자리씩 비교를 하면서, S1[i] == S2[j] 이면, D[i][j] = D[i-1][j-1] + 1를 만족 할 수 있다. 

S1[i], S2[j] 모두를 LCS로 넣으면, 안넣었을 때와 비교해서 LCS가 1자리 더 늘기 때문이다.

 

S1[i] != S2[j] 이면, D[i][j] = max(D[i-1][j], D[i][j-1]) 이다.

S1[i]를 넣든, S2[j]를 넣든, 둘중 하나를 넣은 값 중 큰 것이 LCS이기 때문이다. (두개가 다르기때문에 LCS가 커질 수 없다.)

 

따라서 코드로 구현하면 다음과 같다.

이 문제에서는 두 string의 길이가 같다는 조건이 없으므로, 공백을 추가해서 길이를 맞춰준다.

import sys
read = sys.stdin.readline

S1 = read().replace('\n', '')
S2 = read().replace('\n', '')

if len(S1) < len(S2):
    N = len(S2)
    S1 += ' ' * (N - len(S1))
else:
    N = len(S1)
    S2 += ' ' * (N - len(S2))


D = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

for i in range(1, N+1):
    for j in range(1, N+1):
        if S1[i-1] == S2[j-1]:
            D[i][j] = D[i-1][j-1] + 1
        else:
            D[i][j] = max(D[i-1][j], D[i][j-1])

print(D[N][N])