[백준/파이썬] 9252번 LCS 2 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 9252번 LCS 2
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

두 문자열의 LCS 길이뿐 아니라 실제 LCS 문자열도 출력하는 문제입니다.

코드

s1, s2 = input(), input()
dp = [[""]*(len(s2)+1) for _ in range(len(s1)+1)]
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]+s1[i-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x: len(x))
m = ""
for row in dp:
    m = max(row+[m], key=lambda x: len(x))
print(len(m),m,sep='\n')

설명

DP 셀에 해당 구간의 LCS 문자열 자체를 저장하고, 최대 길이 문자열을 최종 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---