BOJ 9251 LCS Python

문제

링크:https://www.acmicpc.net/problem/9251

접근

LCS알고리즘을 검색해서 풀었다

코드1

import sys

input = sys.stdin.readline
str1 = input().strip()
str2 = input().strip()

lcs = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]

for x in range(1,len(str1)+1):
    for y in range(1,len(str2)+1):
        if str1[x-1] == str2[y-1]:
            lcs[x][y] = lcs[x-1][y-1] +1
        else:
            lcs[x][y] = max(lcs[x-1][y],lcs[x][y-1])
print(lcs[-1][-1])

우선 비교할 문자열을 입력받아 len(str1)+1, len(str2)+1의 길이만큼의 2차원 배열인 lcs를 선언해 준다
그리고 문자열을 하나씩 비교해가며 lcs 배열에 값을 하나씩 저장해간다
lcs[x][y]에 대해 str1[x-1]과 str2[y-2]의 문자가 서로 같다면 2차원 배열의 기준으로 왼쪽 대각선 위의 값에 +1을 하여 저장해 준다.
(lcs 배열의 길이가 각각의 문자열의 길이 +1을 해준 이유가 문자열의 길이에 맞춰 선언하면 0번째 인덱스에서 에러가 나기 때문)
만약에 서로 같지 않은 경우는 2차원 배열 기준으로 위나 왼쪽 중 큰 값을 저장한다

그렇게 하나씩 채워나가면 lcs의 맨 마지막 요소에는 str1, str2에 대해 최장 공통부분 수열의 길이가 저장되어 lcs[-1][-1]의 값을
출력해 줬다

파이썬은 시간제한이 2초라 통과되었다