[백준] 9251번 LCS (LIS 문제)

사용 언어 - Python3

문제 -  9251번 LCS

LIS/LCS 문제 : 가장 긴 증가하는 부분 수열

LIS (Longest Incresing Subsequence)

LCS (Longest Common Subsequence)

 

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

9251번: LCS

 

 

정답

해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기

dp[i] = max(dp[i], dp[j]+1)

 

완전탐색 방법) 수열1 ACAYKP 에서 만들 수 있는 모든 부분수열을 꺼낸다 

[A]

[A,C], [A,A], [A,Y], [A,K], [A,P]

[A,C,A], [A,C,Y] .....

=> 시간 복잡도 문제 있다 !

 

LCS(M,N) = ACAK

if 가장 끝에 있는 문자가

같다면) 하나씩 때서 없애주고 +1 을 해준다.

다르다면) 정답에 영향을 주지 않는 친구를 없애준다. (P, K에서 P는 정답 ACAK에 영향을 주지 못하고 있다.) 

m = list(str(input()))
n = list(str(input()))

dp = [[0 for _ in range(len(n)+1)] for _ in range(len(m)+1)]

for i in range(1,len(m)+1):
    for j in range(1,len(n)+1):
        if m[i-1] == n[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(m)][len(n)])

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/9251_LCS.py