백준 / LCS / 9251번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 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 알고리즘을 이용한 풀이를 사용하시면 쉽게 해결하실 수 있습니다!