9251: LCS (Longest Common Subsequence, 최장 공통 부분 문자열)

Substring과 Subsequence의 차이

• Substring: 전체 문자열에서 연속된 부분 문자열
• Subsequence: 전체 문자열의 부분 문자열 (연속되진 않아도 됨, 순서만 맞으면 됨)

LCS -> Dynamic programming으로 해결

• 비교하고자 하는 문자열을 각각 행, 열로 배치
• 문자를 비교하여 같았을 때 -> 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값 + 1
• 문자를 비교하여 달랐을 때 -> 현재 칸에 들어갈 값은 왼쪽과 위쪽의 값 중 더 큰 값으로

string1 = input()
string2 = input()
#string1 = "ACAYKP"
#string2 = "CAPCAK"

row = len(string2)
col = len(string1)

table = [[0 for j in range(col+1)] for i in range(row+1)]

for i in range(1, row+1):
    for j in range(1, col+1):
        if string2[i-1] == string1[j-1]: #대각선 왼쪽 위의 값 + 1
            table[i][j] = table[i-1][j-1] + 1
        else:
            table[i][j] = max(table[i][j-1], table[i-1][j])

#print(table)
print(table[row][col])

LCS문제는 table을 이용하는 DP로 해결해야 한다는 사실만 알면 쉽게 풀 수 있다.