문제 설명

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력 조건

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력 조건

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

전체 코드

import sys

str1 = sys.stdin.readline().rstrip()
str2 = sys.stdin.readline().rstrip()

dp = [[0] * len(str2) for _ in range(len(str1))]

for i in range(len(str1)):
    for j in range(len(str2)):
        if str1[i] == str2[j]:
            if i - 1 >= 0 and j - 1 >= 0 and dp[i - 1][j - 1] > 0:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 1

answer = 0
for i in range(len(str1)):
    for j in range(len(str2)):
        answer = max(answer, dp[i][j])

print(answer)

두 문자열의 길이가 최대 4000이기 때문에 순열 등의 재귀 또는 브루트 포스 알고리즘으로는 시간초과로 풀 수 없다.
처음에 보고 dp + 문자열인 것 같긴 했으나, 어떻게 풀어야 할지 감을 잡을 수 없었다.
다른 해설들을 참고해보니 두 문자열 길이로 행과 열이 구성된 이차원 배열을 구성하여 dp를 적용한다.

문자열 1의 i번째와 문자열 2의 j번째가 같으면, (i-1,j-1) 값을 보고 결정한다. (i-1,j-1)의 값은 이전까지 결정된 연속된 문자열의 길이다. 만약 0이라면 연속해서 같은 값이 나오지 않은 것이고, 1이상이라면 연속된 문자열이라는 뜻이다.

즉, 이차원 배열이라는 공간을 희생해서 시간적 효율을 얻는, 메모이제션을 활용하는 것이다. 사실 잘 알려진 dp 문제인데... 복습 좀 해야겠다.