백준9251(LCS) - python

 

접근

일단 LCS가 어떤건지 기억이 안나 관찰하면서 감을 잡았다. ACAYK와 CAPCAK에 대한 LCS로 ACAK라고 한다.

두문자열이 있을때 첫번째 문자의 1,2,3,5 인덱스에서 ACAK를 찾을 수 있고 2,4,5,6 인덱스에서 ACAK를 찾을 수 있다.

그리고 2개의 문자열을 놓고 각 자리까지의 LCS를 직접구해보았다.

   A C A Y K P

C 0 1 1 1 1 1

A 1 1 2 2 2 2

P 1 1 2 2 2 3

C 1 2 2 2 2 3

A 1 2 3 3 3 3

K 1 2 3 3 4 4

이렇게 직접 구했는데 점화식을 알기가 너무 어려웠다. 같을 때 1이 올라가고 다를때는 옆과 밑에서 값을 가져오면 된다는건 직접 구하면서

느꼈는데 코딩으로 옮길때 1행과 1열쪽이 어떻게 구해야하는지 감이 오지않았다. 1개 문자열이 아무리 길어져도 나머지 문자열 자리가 1자리니 최대 1이 나오는건 알겠는데 2행 1열, 5행1열 모두 A로 같은데 둘다 1이 나오니 코딩을 어떻게 해야할지 감이오지 않았다. 고민 끝에 왼쪽 대각선 상단에서 +1을 더하는게 최대겠구나 라는 생각이 들어서 점화식을 세울 수 있었다.

 

같을때

dp[i][j] = dp[i-1][j-1]+1

안같을때

dp[i][j] = max(dp[i-1][j],dp[i][j-1])

나의코드

import sys
input = sys.stdin.readline


str1 = list(map(str,input().rstrip()))
str2 = list(map(str,input().rstrip()))
l1 = len(str1)
l2 = len(str2)
L = [[0 for _ in range(l2+1)] for _ in range(l1+1)]

for i in range(1,l1+1):
    for j in range(1,l2+1):
        if str1[i-1] == str2[j-1]:
            L[i][j] = L[i-1][j-1]+1
        else:
            L[i][j] = max(L[i-1][j],L[i][j-1])
print(L[l1][l2])

그리고 코드를 보면 바로전에있는 행을 사용하니 배열 한개를 이용해서도 이를 구현할 수 있을거같다는 생각을 했다.

나의 코드

import sys
input = sys.stdin.readline


str1 = list(map(str,input().rstrip()))
str2 = list(map(str,input().rstrip()))
l1 = len(str1)
l2 = len(str2)
L = [0 for _ in range(l2+1)]

for i in range(1,l1+1):
    pre = 0
    for j in range(1,l2+1):
        if pre < L[j]:
            pre = L[j]
        elif str1[i-1] == str2[j-1]:
            L[j] =pre+1
        else:
            L[j] = max(L[j-1],L[j])
print(L[l2])