*문제 출처는 백준에 있습니다.
문제 제목: LCS / 9251번 (골드 5단계)
문제 사이트: https://www.acmicpc.net/problem/9251
문제 설명

나의 풀이
string_a = ' ' + input()
string_b = ' ' + input()
# dp[i][j]는 string_a의 i번째 문자까지, string_b의 j번째 문자까지의 LCS 길이
dp = [[0] * len(string_b) for _ in range(len(string_a))]
for i in range(1, len(string_a)):
for j in range(1, len(string_b)):
if string_a[i] == string_b[j]:
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]) # 또는 dp[len(string_a) - 1][len(string_b) - 1]

※ 알아야 할 것

LCS 알고리즘을 이용한 풀이를 사용하시면 쉽게 해결하실 수 있습니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 수열 / 2559번 / Python (0) | 2025.04.13 |
|---|---|
| 백준 / N번째 큰 수 / 2075번 / Python (0) | 2025.04.11 |
| 백준 / 두 용액 / 2470번 / Python (0) | 2025.04.09 |
| 백준 / 최소 스패닝 트리 / 1197번 / Python (0) | 2025.04.08 |
| 백준 / 친구 네트워크 / 4195번 / Python (0) | 2025.04.07 |