[백준/파이썬] 9251 LCS

#문제링크

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

9251번: LCS

#나의풀이

import sys

if __name__=="__main__":
    A = sys.stdin.readline().strip()
    B = sys.stdin.readline().strip()
    dp = [0] * len(B)

    for i in range(len(A)):
        cnt = 0
        for j in range(len(B)):
            if cnt < dp[j]:
                cnt = dp[j]
            elif A[i] == B[j]:
                dp[j] = cnt + 1
    print(max(dp))

#해설

LCS에 기본이 되는 문제

방식은 2차원dp와 1차원 dp 2가지를 쓰는 방법이 있는거 같고 메모리 생각했을때 1차원 dp를 사용하는게 좋다고

생각하여 1차원 dp를 사용 했습니다. 시간 자체는 똑같을꺼 같습니다.

 

2중루프로 각 문자열을 접근하고 cnt는 현재 최대값을 의미합니다.

만약 cnt보다 방문하는 dp값이 더 크다면 이미 다른 문자가 방문했다는것을 의미합니다. 따라서 최대값만 갱신해줍니다.

elif문으로 cnt가 dp값과 같거나 크고 문자가 같다면 방문하지 않았다는것으로 현재 dp값을 최대값 + 1로 갱신해줍니다.

 

자세한 설명은 아래 블로그에서 참고하였습니다.

#출처

https://myjamong.tistory.com/317

백준 9251 파이썬 - LCS - 동적 계획법