백준 9251번 : LCS

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

9251번: LCS

 

접근 방법을 생각하지 못해 해답을 보고 푼 문제이다.

 

주어진 두 문자열의 부분 수열 중, 공통으로 들어있는 가장 긴 부분 수열의 길이를 구하는 문제다. 처음 떠오른 생각은 두 문자열의 부분 수열을 모두 구하고 비교하려고 했다. 문자열의 길이가 최대 1000이기 때문에 당연히 불가능하지만 이 방법밖에 머릿속에 떠오르지 않았다.

다이내믹 프로그래밍의 메모이제이션 방법을 사용하려면 답을 계산하는 과정에서 중복되는 부분이 생겨야 하는데, 그렇게 만들기 위한 과정을 떠올리지 못해서 풀이를 참고했다.

 

우리가 주목해야할 것은 '공통' 부분 수열이다. 이 공통 부분 수열은 두 문자열에 모두 들어있기 때문에 공통 부분 수열이 만들어지는 과정에 주목할 필요가 있다. 예를 들어 처음에 "A"라는 문자열과 "B"라는 문자열이 있다고 가정하자. 두 문자열의 부분 수열은 각각 자기 자신으로 공통되는 부분 수열이 없다. 여기서 "A"문자열에 'B'가 합쳐져 "AB"가 되었다고 하면 두 문자열의 공통 부분 수열은 "B"가 된다. 즉, 두 문자열의 마지막 문자가 같은 시점에 공통 부분 수열의 길이가 증가한다. 두 문자열의 마지막 문자가 공통되므로 공통 부분 수열에 그 문자가 추가되어 길이가 증가하는 것이다. 이번엔 "B" 문자열에 'C'가 합쳐져 "BC"가 됐다. 하지만 두 문자열의 마지막 문자가 다르기 때문에 공통 부분 수열의 길이 변화는 없다. 이 상황에서 "AB" 문자열에 'C'가 합쳐진다면 두 문자열의 마지막 문자가 같으므로 기존의 공통 부분 수열 "B"에 'C'가 추가되어 "BC"가 된다.

 

정리하자면 두 문자열을 첫 문자부터 확장시켜가면서 현재까지의 공통 부분 수열의 길이를 기록한다. 위에서 말한것처럼 두 문자열의 마지막 문자가 같을 때 길이가 증가하고 같지 않다면 '이전'의 공통 부분 수열의 길이를 저장하면 된다. 여기서 '이전' 이란 두 문자열에서 마지막 문자가 각각 붙기 전의 문자열 상태를 의미한다.

 

아래 두 코드는 순서대로 반복문과 재귀를 이용한 풀이이다.

s1 = ' ' + input().rstrip()
s2 = ' ' + input().rstrip()
l1, l2 = len(s1), len(s2)
d = [[0]*l2 for _ in range(l1)]

for i in range(1, l1):
    for j in range(1, l2):
        if s1[i] == s2[j]:
            d[i][j] = d[i-1][j-1] + 1
        else:
            d[i][j] = max(d[i][j-1], d[i-1][j])
print(d[l1-1][l2-1])

import sys
sys.setrecursionlimit(10**7)

def sol(i, j):

    if i < 0 or j < 0:
        return 0

    if d[i][j] >= 0:
        return d[i][j]

    if s1[i] == s2[j]:
        d[i][j] = 1 + sol(i-1, j-1)
    else:
        d[i][j] = max(sol(i-1, j), sol(i, j-1))

    return d[i][j]

s1, s2 = input().rstrip(), input().rstrip()
d = [[-1]*1000 for _ in range(1000)]
print(sol(len(s1)-1, len(s2)-1))