[백준/파이썬] 9251번 LCS 풀이

---

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

---

문제 정보

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

풀이

문제

두 문자열의 최장 공통 부분 수열(LCS) 길이를 구하는 문제입니다.

코드

s1, s2 = input(), input()
dp = [[0]*(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]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = 0
for row in dp:
    m = max(m, max(row))
print(m)

설명

2차원 DP를 이용해 문자 일치 시 대각선+1, 불일치 시 왼쪽/위쪽 최대값을 채워 최종 LCS 길이를 얻습니다.

---

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

---