https://www.acmicpc.net/problem/9251
import sys
input = sys.stdin.readline
if __name__ == "__main__":
a = '0' + input().rstrip() #마진 주기
b = '0' +input().rstrip() #마진 주기
#각 문자열의 길이 찾기
len_a = len(a)
len_b = len(b)
#dp 저장소
lcs = [[0] * (len_b) for _ in range(len_a)]
#lcs 길이 탐구
for i in range(1,len_a):
for j in range(1,len_b):
if a[i] == b[j]:#문자가 같은 경우, 바로 위 대각선 lcs 값에 + 1
lcs[i][j] = lcs[i-1][j-1] + 1
else: #같지 않은 경우 위쪽의 최댓값과 왼쪽의 최댓값중 큰 값
lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])
print(lcs[len_a-1][len_b-1]) #이 문제의 답
#LCS 찾기 -- 이건 문제는 아닌데 공부용
res = ""
i = len_a-1
b = len_b-1
while 1:
if lcs[i][j] == 0:
break #lcs 값이 0 이 나오면 종료 더이상 없다는거
#위나 왼쪽과 같은 값이 있다 -> 같지 않은 값
if lcs[i][j] == lcs[i-1][j]:
i = i-1
elif lcs[i][j] == lcs[i][j-1]:
j = j-1
#위나 왼쪽에 같은 값이 없다?대각선 위로 올라가고 그 값이 공통 값이므로 추가해주기
else:
res += a[i]
i = i-1
j = j-1
print(res[::-1])
2가지 경우의 수로 나누어서 점화식을 세워볼 수 있다.
마지막 문자를 제외한 나머지 문자열의 갯수를 구하면 된다.
LCS[i][j] = LCS[i-1][j-1] + 1
주어진 첫번째 문자열에서 문자를 제외한 경우와 두번째 문자열에서 문자를 제외한 경우 중 큰 값을 구한다.
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
LCS 2차원 배열을 생성하여 Bottom-Top 방식으로 위의 점화식을 계산하여 배열을 채워넣은 후 가장 max 값 LCS[첫번째 배열의 문자열 길이][두번째 배열의 문자열 길이] 가 최종 정답이 된다.
[[0] * lenb for _ in range(lena)] 이렇게 세팅을 해놓고 아래 이중 For문을 돌릴 때 행과 열 잘못 설정해서 index error 남;;; 잘 체크하자