문제
접근
DP 문제이다.
문자열의 길이를 하나씩 늘려주면서 DP table을 채워나가면 된다.
문제에 주어진 예시로 확인해보자.
S1 = ACAYKP
S2 = CAPCAK
일 때,
s1 = A
s2 = C
이 때 LCS는 0.
s1 = A
s2 = CA
이 때 LCS는 1.
….
s1 = A
s2 = CAPCAK
이 때 LCS는 1.
s2를 끝까지 돌았으니, s1을 한자리 늘려주고 다시 반복.
s1 = AC
s2 = C
이 때 LCS는 1.
이런 식으로 끝까지 돌면 된다.
table을 직접 채워주면서 따라가보면 규칙이 보인다.
가장 마지막에 추가된 문자들이 서로 같을 때, LCS를 1 늘릴 수 있다.
기준은 마지막 문자들이 추가되기 이전 상태에서 가장 긴 LCS에 +1을 해주면 된다.
서로 다른 문자라면 이전 상태 중에 가장 긴 LCS를 그대로 가진다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def main():
str1 = list(str(input()))
str2 = list(str(input()))
dp = [[0] * (len(str2)+1) for _ in range(len(str1)+1)]
for i, s1 in enumerate(str1):
for j, s2 in enumerate(str2):
if s1 == s2:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
print(dp[-1][-1])
if __name__ == "__main__":
main()