반응형
풀이
LCS 알고리즘의 대표적인 문제다. LCS 알고리즘에 대해서는 여기를 참고하자.
코드
if __name__ == '__main__':
str1 = input()
str2 = input()
dp = [[0 for _ in range(len(str1) + 1)] for _ in range(len(str2) + 1)]
for i in range(1, len(str2) + 1):
for j in range(1, len(str1) + 1):
if str1[j-1] == str2[i-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[len(str2)][len(str1)])
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
2467. 용액 (Python) (0) | 2022.05.12 |
---|---|
2660. 회장뽑기 (Python) (0) | 2022.05.11 |
2580. 스도쿠 (Python) (0) | 2022.05.01 |
17472. 다리 만들기 2 (Python) (0) | 2022.04.30 |
2513. 통학버스 (Python) (0) | 2022.04.30 |
댓글