https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
X와 Y의 문자열이 같다면, dp[i][j] = 대각선+1
X와 Y의 문자열이 다르다면, dp[i][j] = max(왼쪽값, 위값)
X = input()
Y = input()
dp = [ [0] * (len(Y)+1) for _ in range(len(X)+1) ]
for i in range(len(X)):
for j in range(len(Y)):
if X[i] == Y[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(X)][len(Y)])
'알고리즘 > 백준 (Pyhthon)' 카테고리의 다른 글
| [알고리즘] 백준 17389 보너스점수 / python (0) | 2020.02.25 |
|---|---|
| [알고리즘] 백준 17269 이름궁합 테스트 / python (0) | 2020.02.24 |
| [알고리즘] 백준 11053 가장 긴 증가하는 부분수열 / python (0) | 2020.02.11 |
| [알고리즘] 백준 12865 평범한 배낭 / python (0) | 2020.02.11 |
| [알고리즘] 백준 1904 01타일 / python (0) | 2020.02.09 |
