[백준] 9252번 LCS 2 - 파이썬(Python)

문제 (링크)

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

9252번: LCS 2

 

나의 풀이

import sys
input = sys.stdin.readline

seq_1 = input().rstrip()
seq_2 = input().rstrip()

n = len(seq_1)
m = len(seq_2)

arr = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(1, n+1):
        if seq_1[j-1] == seq_2[i-1]:
            arr[i][j] = arr[i-1][j-1] + 1
        
        else:
            arr[i][j] = max(arr[i-1][j], arr[i][j-1])

print(arr[m][n])

if arr[m][n] != 0:
    current_x = m
    current_y = n
    result = ""
    while current_x != 0 and current_y != 0:
        if seq_1[current_y-1] == seq_2[current_x-1]:
            result += seq_1[current_y-1]
            current_x -= 1
            current_y -= 1
        
        else:
            if arr[current_x][current_y] == arr[current_x-1][current_y]:
                current_x -= 1
            
            elif arr[current_x][current_y] == arr[current_x][current_y-1]:
                current_y -= 1

    print(result[::-1])

 

풀이법 및 코드 설명

LCS 알고리즘을 구현해볼 수 있는 문제이다.

 

LCS 값을 담을 2차원 배열을 만들 때 i와 j가 0일 때는 모두 0으로 값을 초기화해줘야 하기 때문에 인덱스가 약간 헷갈릴 수 있지만, 

 

조금만 집중하면 오류 없이 구현할 수 있다.

 

부분 수열을 구하는 문제 역시 arr[m][n]에서부터 시작하여 거꾸로 올라가며 구할 수 있다.