[백준 | python] #9251 LCS (DP)

알고리즘 분류 > 문자열 > LCS

 

 

LCS Lv.골드5

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

 

 

 

첫 번째 풀이 :     실패

n = input()
m = input()
ans = 0
for i in range(len(n)):
    for j in range(i, len(m)):
        if n[i] == m[j]:
            ans+=1
            break
print(ans)

• 가장 긴 걸 찾아야 되는데
• 처음에 문자가 같다고 판단하면 거기서 멈춤

 

 

 

 

두 번째 풀이:     100점

import sys

string_a = ' ' + sys.stdin.readline().rstrip()
string_b = ' ' + sys.stdin.readline().rstrip()
dp = [[0] * len(string_b) for _ in range(len(string_a))]

for i in range(1, len(string_a)):
    for j in range(1, len(string_b)):
        if string_a[i] == string_b[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            
print(dp[-1][-1])

• 참고 =>  출처 [https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-9251-LCS-%ED%8C%8C%EC%9D%B4%EC%8D%AC]