[알고리즘 스터디] 백준 #9251 LCS

문제 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제.

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

=> 연속하지 않아도 된다는 것이 포인트.

풀이

2차원 cache를 이용한 DP 방식으로 풀면 된다. 말로 풀어 쓴 것은 이해하기 힘드므로 그림을 그려보았다.

s1 = ACAYKP

s2 = CAPCAK 를 입력했을 때 cache의 모습이다.

cache[i][j]에는 s1의 i 번째와 s2의 j 번째가 같을 때 값이 채워진다. (같지 않은 경우에는 0이 채워진다)

둘이 같을 때, 그냥 1을 채우는 것이 아니라 지난 구역에서 가장 큰 값+1을 채운다.

첫 번째 그림에서 빨간색 칸을 채우기 위해 파란색 칸들을 고려해야 한다. 

두 번째 그림에서는 각각 분홍색과 보라색 칸이 어떻게 채워지는지 표시해두었다.

이러한 규칙으로 cache를 채워나가면 된다. 

제일 마지막 row에 최댓값이 있을 것이란 보장이 없으므로 

각 column별로 최댓값을 저장하는 배열을 사용해서 맨 마지막에는 이 배열안에서 최댓값을 찾으면 된다.

 

코드 

#include <stdio.h>
#include <string.h>

using namespace std;
int main() {
	char str1[1001];
	char str2[1001];

	scanf_s("%s", str1);
	scanf_s("%s", str2);

	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int cache[1001][1001] = { 0, };

	int maxC[1001] = { 0, };
	int after[1001] = { 0, };
	int M;
	for (int i = 0;i < len1;i++) {
		for (int j = 0;j < len2;j++)
			maxC[j] = after[j];
		for (int j = 0;j < len2;j++) {
			if (str1[i] == str2[j]) {
				M = 0;
				for (int k = 0;k < j;k++) {
					if (M < maxC[k])
						M = maxC[k];
				}
				cache[i][j] = M + 1;
				if (M + 1 > maxC[j])
					after[j] = M + 1;
			}
		}
	}
	int result = 0;
	for (int i = 0;i < len2;i++) {
		if (result < after[i])
			result = after[i];
	}
	printf("%d", result);
	printf("\n");
	}*/
}

maxC (각 column별 최댓값을 저장하는 배열) 을 한 row가 끝나기 전에 업데이트하면, 제대로된 결과가 나오지 않기 때문에 after배열을 만들어서 이용하였다.

 

제출 결과