728x90
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
1. 코드 설명
두줄로 들어오는 문자열의 부분 문자열중에 최다 길이.
부분 수열하고 비슷한듯 다른 문제.
2. 예
A C A Y K P
C A P C A K
부분 문자열중에 가장 긴 문자열은 ACAK이다.
3. 코드
s1 = input()
s2 = input()
dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i] == s2[j]:
dp[i+1][j+1] = dp[i][j] + 1
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
print(dp[len(s1)][len(s2)])서로 비교해 나가면 같다면 대각선 아래에 +1 값을 넣는다.
같지 않다면 위와 왼쪽중 큰 값을 넣는다.
| A | C | A | Y | K | P | ||
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| P | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
| K | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
| 0 | 1 | 2 | 3 | 3 | 4 | 4 |
dp 리스트에 맨 마지막 값을 출력하면 가장 긴 부분 문자열의 길이가 나온다
728x90