문제 링크
https://www.acmicpc.net/problem/9252
🕒 Python 풀이시간: 60분
import sys
input=sys.stdin.readline
s1=list(input())[:-1]
s2=list(input())[:]
dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
answer=""
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1]==s2[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(s1)][len(s2)])
longest=dp[len(s1)][len(s2)]
j=len(s2)
prev=len(s2)
for i in range(len(s1),-1,-1):
find=False
while j>=0:
if s1[i-1]==s2[j-1]:
if dp[i][j]==longest:
if dp[i-1][j]==dp[i][j-1] and dp[i-1][j]==dp[i-1][j-1]:
answer=s1[i-1]+answer
longest-=1
prev=j-1
j=j-1
find=True
break
j-=1
if not find:
j=prev
print(answer)최장 공통 문자열 찾기: DP로 해결하는 숨겨진 비밀! 🔍
공통된 최장 문자열을 구해야 하므로 DP를 활용할 수 있다. 최대 문자열의 길이가 1,000이기 때문에 이중 for문을 통해 DP를 갱신한다하더라도 1,000,000으로 0.1초 이내에 충분히 가능하다.
현재까지의 문자의 상황을 DP에 현재까지 문자열을 탐색했을 때의 최대 길이로 나타낼 수 있으므로 DP를 이와 같이 갱신하면 된다. 즉, 현재 문자가 같을 경우에는, 길이를 늘릴 수 있으므로, dp[i-1][j-1]에 길이를 1 늘려주면 되고 그렇지 않을 경우에는 전의 문자열의 길이와 같으므로 그 전 문자열의 길이 중 긴 길이로 가져가 주면된다. 이렇게 dp를 끝까지 갱신하면 마지막 문자열까지 탐색했을 때의 길이의 최대 값이 최장 길이가 된다.
최장 길이가 되는 문자열은 역으로 탐색해나가 주면 된다. 최장 길이를 기준으로 배열의 끝에서부터 같아서 길이가 갱신된 순간을 찾는다. 그렇게 찾았다면 그 다음의 문자는 현재의 문자보다 앞쪽에 위치해야 하므로 그 영역을 줄인 영역에서 현재의 길이보다 -1이 된 길이로 dp에서 찾아주면 된다. 이렇게 찾아주면 최장 길이를 만드는 문자열을 완성시킬 수 있다.
이렇게 Python로 백준의 "LCS 2" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
