[Baekjoon] LCS / Python, 파이썬 / 9251
2022. 11. 23. 15:23ㆍBaekjoon/Gold
728x90
반응형
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제 설명
더보기
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예제 입력 1
ACAYKP
CAPCAK
예제 출력 1
4
문제 풀이
import sys
input = sys.stdin.readline
word_1 = str(input().strip())
word_2 = str(input().strip())
dp = [[0] * (len(word_2) + 1) for _ in range(len(word_1) + 1)]
for i in range(1, len(word_1) + 1):
for j in range(1, len(word_2) + 1):
if word_1[i - 1] == word_2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
print(dp[len(word_1)][len(word_2)])
728x90
반응형
'Baekjoon > Gold' 카테고리의 다른 글
[Baekjoon] 해킹 / Python, 파이썬 / 10282 (0) | 2022.11.28 |
---|---|
[Baekjoon] 가장높은탑쌓기 / Python, 파이썬 / 2655 (0) | 2022.11.23 |
[Baekjoon] 평범한 배낭 / Python, 파이썬 / 12865 (0) | 2022.11.23 |
[Baekjoon] 문제집 / Python, 파이썬 / 1766 (0) | 2022.11.23 |
[Baekjoon] 카드 정렬하기 / Python, 파이썬 / 1715 (0) | 2022.11.22 |