[백준 9252번] 파이썬 - LCS2

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

9252번: LCS 2

 

 

# 조건

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

 

# 접근 방법

• 최대 길이가 1000자 이므도 2중 for문을 돌려도 충분한 길이가 나온다.
• ACAYKP와 CAPCAK의 길이에 맞는 2차원 배열을 생성한 후 2번째 문자열을 첫 번째 문자열과 비교하며 반복문을 돌려준다.
  • C의 경우 타겟 문자열에 존재하므로 타켓문자열의 C가 시작하는 부분부터 1로 채워준다.
  • 이후 A도 존재하는데 이 때, 1로 채워주며 바로 직전 행의 값들을 더해준다.
  • 즉, 2번째 행의 값은 1 2 1 1 1 1 이 되는 것
  • 이런 식으로 모두 구한다면 최장 길이가 구해진다.
• 이번엔 최장 길이의 수열을 구하기 위해서 역추적을 해준다.
  • 예시의 경우 ACAK로 4이므로 가장 마지막 행에서 4가 시작되는 곳을 찾아준다.
  • 찾았다면 -1 해주고 한 행위로 올라가는데
  • 만약, dp[i-1][j] = dp[i][j] 이면 dp[i-1][j] 로 이동하고,
  • dp[i][j-1] == dp[i][j]이면 dp[i][j-1]로 이동한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
a = input().rstrip()  
b = input()  
  
dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)]  
  
for i in range(1, len(b) + 1):  
    for j in range(1, len(a) + 1):  
        if a[j - 1] == b[i - 1]:  
            dp[i][j] = dp[i - 1][j - 1] + 1  
        else:  
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  
  
def findit():  
    ans = ''  
    now = dp[-1][-1]  
    y = len(dp) - 1  
    x = len(dp[0]) - 1  
  
    while now != 0:  
        if dp[y][x - 1] == now - 1 and now - 1 == dp[y - 1][x]:  
            ans = a[x - 1] + ans  
            now -= 1  
            y -= 1  
            x -= 1  
        else:  
            if dp[y - 1][x] > dp[y][x - 1]:  
                y -= 1  
            else:  
                x -= 1  
    return ans  
  
print(dp[-1][-1])  
print(findit())