[백준 9251번] 파이썬 - LCS

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

9251번: LCS

 

 

# 조건

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

 

# 입력

• 첫째 줄과 둘째 줄에 두 문자열이 주어진다.
• 문자열은 알파벳 대문자로만 이루어져있으며, 최대 1000글자로 이루어져 있다.

 

# 접근 방법

• dp를 이용하여 최장 증가 수열을 찾아준다.
• LCS 참고
  • https://cheon2308.tistory.com/entry/Algorithm-%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-LCS
• 둘 중 하나를 기준으로 삼아서,
• 같은 문자열이 나온다면 i-1, j-1 값에서+1을 해주고
• 아니라면, i-1 또는 j-1에서 큰 값을 선택해준다.

import sys  
sys.stdin = open('input.txt')  
  
def LCS(X,Y):  
    X = ' '+X  
    Y = ' '+Y  
    dp = [[0] * (len(Y)) for _ in range(len(X))]  
    for i in range(1,len(X)):  
        for j in range(1,len(Y)):  
            if X[i] == Y[j]:  
                dp[i][j] = dp[i-1][j-1] + 1  
            else:  
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  
  
    return dp[len(X)-1][len(Y)-1]  
  
  
  
a = input()  
b = input()  
c=LCS(a,b)  
print(c)