LCS2 9252번

’’’ 시간 제한 ‘’’

1초

’’’ 메모리 제한 ‘’’

256MB

’’’ Problem ‘’’

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

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

’’’ Input ‘’’

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

’’’ Output ‘’’

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

’’’ 설명 ‘’’

두 수열중의 부분 수열을 찾아내는 문제다.

두 수열을 DP의 인덱스로 잡고 표를 그려보면

두 부분수열이 공통부분이 생겼을때,

dp[i][j] = dp[i-1][j-1] + 1;

두 부분수열이 같지 않을 때.

dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

이를 조합하여 점화식을 작성하면 다음과 같다.