[BOJ] #9251 LCS

LCS

백준 #9251

---

📌 문제

예제 입력

ACAYKP
CAPCAK

예제 출력

4

---

📌 풀이

Logic

• 두 문자열 입력 받기
• DP 테이블 생성
  • 2차원 배열 DP는 str1의 처음 i글자와 str2의 처음 j글자 까지의 LCS 길이를 저장
  • str1[i - 1]와 str2[j - 1]이,,,
    • 같으면 공통 문자를 LCS에 추가
    • 다르면 둘 중 더 긴 LCS 선택
• DP[-1][-1] 출력 <- 최댓값

# 변수명
str1, str2 : 비교할 두 문자열

Python

import sys

str1 = sys.stdin.readline().strip()
str2 = sys.stdin.readline().strip()

dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        if (str1[i - 1] == str2[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[-1][-1])

---

✏️ 새로운 내용

-

---

📚 회고

💡 Solved.ac

• 이번 문제로 DP 유형의 문제 복습을 마무리 하려고 한다.
• 다음으로 그리디 알고리즘 문제들에 도전해보려고 한다.