ShaShaKa Dev Note

LCS

10 August 2019

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

이번은 LCS(Longest Common Subsequence)를 구하는 문제를 풀어보도록 하겠습니다.

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

#define max(a,b) (((a)>(b))?(a):(b))

static char* first;
static char* second;
static int** lcs_arr;

void init();
int lcs(int i, int k);

int main(void) {

	init();

	printf("%d\n", lcs(strlen(first) - 1, strlen(second) - 1));

	return 0;
}

void init() {
	first = new char[1000];
	second = new char[1000];
	scanf("%s", first);
	scanf("%s", second);

	lcs_arr = new int*[strlen(first)];
	for (int i = 0; i < strlen(first); i++)
	{
		lcs_arr[i] = new int[strlen(second)];
		for (int k = 0; k < strlen(second); k++)
		{
			lcs_arr[i][k] = -1;
		}
	}
}

int lcs(int i, int k) {
	if (i == -1 || k == -1)
	{
		return 0;
	}

	if (lcs_arr[i][k] == -1)
	{
		if (first[i] == second[k])
		{
			lcs_arr[i][k] = lcs(i - 1, k - 1) + 1;
		}
		else {
			lcs_arr[i][k] = max(lcs(i - 1, k), lcs(i, k - 1));
		}
	}

	return lcs_arr[i][k];
}

두 수열이 주어졌을 때, 각각의 수열을 a(i), b(k)라고 생각하고, 두 수열에서 해당 길이까지 가장 긴 부분 수열의 길이를 lcs(a(i), b(k))라고 정의해봅시다.
만약 마지막 문자의 값이 똑같다면 lcs(a(i), b(k)) = lcs(a(i-1), b(k-1)) + 1 과 같습니다.
만약 마지막 문자의 값이 다르다면 lcs(a(i), b(k)) = MAX(lcs(a(i), b(k-1),lcs(a(i-1), b(k)) 로 정의할 수 있습니다.
예를 들면, 각각의 수열을 아래로 정의합니다.
ACAYKP
CAPCAK

마지막 문자가 다르므로 최대 길이는 MAX(lcs(ACAYKP,CAPCA), lcs(ACAYK,CAPCAK))와 같고,
lcs(ACAYK,CAPCAK)에서는 마지막 문자가 같으므로, lcs(ACAYK,CAPCAK) = lcs(ACAY,CAPCA) + 1 과 같습니다.
메모이제이션을 이용해 각각의 값을 arr에 저장해주고, 함수를 만들어 return 하도록 합니다.