[Python | 파이썬] 백준 9251 LCS

[Python | 파이썬] 백준 9251 LCS 

 

LCS Longest Common Subsequence 최장 공통 부분수열 문제는 dp를 이용해서 풀 수 있다.

두 개의 문자열에 대해서 최대한 겹치는 문자열의 길이를 출력하는 문제이다.

b문자열을 열 - 가로로 일직선 방향에 두고 a문자열을 행 - 세로로 일직선 방향에 두고 인덱스를 증가시키면서 확인한다.

우선 0 <= i <= len(a)에 대해서 dp[i][0] 과 0 <= j <= len(b) 에 대해서 dp[0][i]는 모두 0으로 초기화한 상태에서 시작한다.

그리고 먼저 a[0]에 대해서 b[0]~b[len(b)-1]까지 비교하면서 a[0]와 b[j]가 같다면 dp[1][j]를 dp[0][j-1]의 값보다 1증가시키고 같지 않다면 dp 테이블 상의 왼쪽과 위쪽의 값 중 더 큰 값으로 갱신한다. (dp[1][j-1] 또는 dp[0][j])

그리고 a[0]을 b[0]~b[len(b)-1]까지 확인한 것 처럼 1 <= i <= len(a)까지 i를 증가시키고 각 인덱스에 대해서 1 <= j <= len(b) 까지 증가시키면서 a[i-1]을 b[j-1]과 비교하면 된다.

a = input()
b = input()
dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]

max_value = 0
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
print(dp[len(a)][len(b)])

 

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

9251번: LCS