백준(baekjoon) 9251번: LCS(골드 5, 파이썬 PYTHON) - 동적 계획법 1

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

https://www.acmicpc.net/problem/9251

9251번: LCS

 

import sys

A=list(sys.stdin.readline().rstrip())
B=list(sys.stdin.readline().rstrip())
dp=[[0 for _ in range(len(A)+1)]for _ in range(len(B)+1)]

for x in range(1,len(B)+1):
  for y in range(1,len(A)+1):
    if(B[x-1]==A[y-1]):
      dp[x][y]=dp[x-1][y-1]+1
    else:
      dp[x][y]=max(dp[x-1][y],dp[x][y-1])

print(dp[len(B)][len(A)])

 

※ 동적 계획법 1

 

 

● 입력되는 수열을 배열로 만들어서 각각 A, B 에 저장해준다. 그리고 행의 크기가 len(B)+1, 열의 크기가 len(A)+1 이고 초기값이 0인 2차원배열 dp를 정의해준다.(dp[x][y] 에 저장될 값은 A[0] 부터 A[y-1] 까지의 수열과 B[0] 부터 B[x-1] 까지의 수열 모두의 부분 수열이 되는 수열 중 가장 긴 수열의 길이이다. x 또는 y가 0인 dp[x][y]의 값은 0으로 고정한다.)

 

● x는 1부터 len(B) 까지, y는 1부터 len(A) 까지 돌아간다. 만약 B[x-1] 과 A[y-1] 의 값이 같으면 B[x-1] 과 A[y-1] 이 포함되지 않은 두 수열 모두의 부분 수열 중 가장 긴 수열의 길이에서 1을 더하면 되므로, dp[x][y] 에 dp[x-1][y-1]+1 의 값을 넣어준다.

 

● B[x-1] 과 A[y-1] 의 값이 다르면 가장 긴 부분 수열의 길이는 A[y-1] 은 포함되지만 B[x-1] 은 포함되지 않은 두 수열 모두의 부분 수열 중 가장 긴 수열의 길이, B[x-1] 은 포함되지만 A[y-1] 은 포함되지 않은 두 수열 모두의 부분 수열 중 가장 긴 수열의 길이 중 더 긴 길이가 되므로 dp[x][y] 에 max(dp[x-1][y] , dp[x][y-1]) 의 값을 넣어준다.

 

● dp[len(B)][len(A)] 에는 모든 문자가 고려된 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 수열의 길이가 저장되어 있으므로 이를 출력해주면 답이 나오게된다!

 

결과