코드 해석 _ LCS(9251)

문제

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

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

입력

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

출력

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

import sys
input = sys.stdin.readline

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

a, b = len(A), len(B)
cache = [0]*b # 누적 값을 저장할 cache 리스트 생성

for i in range(a):
    cnt = 0 # 누적 변수 cnt
    for j in range(b):
    	# 누적 변수의 값이 캐시값보다 작으면 교체
        if cnt < cache[j]:
            cnt = cache[j]
        # 글자가 같은 경우 누적 변수에서 1을 더함 
        elif A[i] == B[j]:
            cache[j] = cnt + 1

# 누적 변수의 값이 해당 위치의 캐시값보다 작은지 여부부터 확인해야 한다!

print(max(cache))

 

글자 하나를 기준으로 1차원 배열을 만들어주고, 같튼 글자를 순회하는 경우 누적 값(cache)에서 1을 더한 값을 넣어주는 방식이다.

순회할 때마다 누적값을 저장할 변수를 하나 사용하고 만약 글자가 다른 경우 누적 변수의 값이 해당 위치의 값보다 작은 경우 해당 값으로 교체한다. 이렇게 하면 누적 값에는 이전 위치까지의 최댓값, 즉 부분 문자열의 최대갯수가 계속해서 저장된다.