[Baekjoon]백준 9251 LCS(골드 5) - Python

문제설명

해당 문제는 두 개의 수열이 주어졌을 때, 두 개의 수열이 공통적으로 가지고 있는 문자열로

가장 긴 부분 수열을 만들고, 그 길이를 출력하는 문제이다

두 개의 수열을 동시에 확인해야하기 때문에 index의 위치를 옮기면서 그 당시의 최대 길이를 저장하는 로직을 생각하였다

그 과정속에서 동적 게획법을 사용하면 시간 제한에 걸리지 않을 수 있을거라고 생각했다

 

로직 작성에 앞서, 두 문자열을 리스트로 변환하여 입력받은 후, 길이를 저장하기 위한 2차원 리스트를 만들어준다

이후에 두 문자열의 길이로 for문을 두개 만들고 index를 이동하며 최대 길이를 찾는다

만약 비교하는 두 문자열이 같다면 +1 한 값을 저장해주고,

아니라면 각각의 이전 index의 값 중에서 최댓값을 저장해주면 된다

이렇게 되면 길이의 최댓값이 저장된 리스트의 가장 마지막 index에 최댓값이 저장된다

first_ch = list(input())
second_ch = list(input())
result = []

for i in range(len(first_ch) + 1):
    row = [0] * (len(second_ch) + 1)
    result.append(row)

# print(first_ch)
# print(second_ch)
# print(result)

for i in range(1, len(first_ch) + 1):
    for j in range(1, len(second_ch) + 1):
        if first_ch[i-1] == second_ch[j-1]:
            result[i][j] = result[i-1][j-1] + 1 # LCS 길이 저장
        else:
            result[i][j] = max(result[i-1][j], result[i][j-1]) # LCS의 길이 최댓값 저장

# print(result)
print(result[len(first_ch)][len(second_ch)])