https://www.acmicpc.net/problem/9251
시간 1초, 메모리 128MB
input :
- 첫째 줄과 둘째 줄에 두 문자열
output :
- 두 문자열의 LCS의 길이를 출력
조건 :
- 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
처음 시도는 재귀를 이용해서 모든 문자열을 만들어 딕셔너리에 저장을 한다면? 메모리 초과가 발생한다 ㅋㅋㅋㅋㅋㅋㅋ
이를 통해 알 수 있는 것은 메모리를 줄여야 한다는것 -> DP를 사용하자.
살짝 그 배낭 문제와 비슷하다는 생각이 든다.
두 문자열 ACAYKP, CAPCAK 가 존재할 때.
a = ACAYKP
b = CAPCAK 라고 보자.
https://suri78.tistory.com/11
오늘의 선생님.
동일한 알파벳이 나오면 왼쪽 대각선위의 값에 +1을 한다.
왜 왼쪽 대각선 위일까?
현재 대입해보고 있는 문자열을 생각해보자.
만약 현재 대입해보고 있는게 'CAP' 일 때 현재 보고 있는것은 'P'가 존재하는지를 보고 있는것이다.
ACAYKP 에는 'P'가 존재한다. 그렇다면 지금까지 가지고 있는 LCS 기록은 어디에 존재할까?
P를 붙이지 않은 'CA' 배열에 값이 존재 할 것이다. 그리고 P는 아직 붙지 않았다고 생각을 하자.
그렇기 때문에 i - 1, j - 1에 존재하는 값을 가져 오는 것이다.
그리고 아무것도 없을 떄, 이전 까지의 LCS 기록중에서 가장 긴 값을 가져 와야 한다.
현재 비교하는게 'CA' / 'AC' 일 떄.
CA / A
C / AC 둘의 값 중에 뭐가 더 큰지를 확인 하는 것과 동일 하다.
모든 경우의 수를 담고 있는 놈을 가지고 오기 위함이다.
솔직히 써놓고도 뭔 말인지 모르긴 .. 똑같은데 ㅋㅋㅋㅋㅋㅋㅋ 뭐 나중에 또 보도록 하자.
import sys
a = list(sys.stdin.readline().strip())
b = list(sys.stdin.readline().strip())
data = [[0] * (len(a) + 1) for i in range(len(b) + 1)]
for i in range(1, len(b) + 1):
for j in range(1, len(a) + 1):
b_idx = i - 1
a_idx = j - 1
if a[a_idx] == b[b_idx]:
data[i][j] = data[i - 1][j - 1] + 1
else:
data[i][j] = max(data[i - 1][j], data[i][j - 1])
print(data[-1][-1])
