[C] 백준 - 9252번: LCS - 2

9월 11일(월) - 다이나믹 프로그래밍 (9252번)

9252번: LCS 2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했던 "9251번: LCS" 문제와 거의 유사

[C] 백준 - 9251번: LCS

 

- 입력으로 들어오는 문자열 2개는 string_1과 string_2로 받는다

  그리고 string_1의 길이는 len_1으로, string_2의 길이는 len_2로 저장한다

- LCS 알고리즘을 이용해서, ( len_1 ) x ( len_2 ) 크기의 표를 채우며

  LCS의 길이인 LCS[ len_1 ][ len_2 ]값을 출력한다

- LCS 알고리즘을 거꾸로 이용해서, ( len_1 ) x ( len_2 ) 크기로 채워진 표를 거꾸로 돌아가며

  print_LCS 함수를 재귀적으로 구현해야한다

 이를 통해 LCS에 해당하는 값들을 출력해야한다

- 출력은 LCS[ ][ ]에서 가장 큰 값을 LCS의 길이로 출력하고, 재귀과정을 통해서 나머지 수열을 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int LCS[1001][1001];
char string_1[1001];
char string_2[1001];

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

void print_LCS(int i, int j)
{
	if (!LCS[i][j])
	{
		return;
	}

	if (string_1[i - 1] == string_2[j - 1])
	{
		print_LCS(i - 1, j - 1);
		printf("%c", string_1[i - 1]);
	}
	else
	{
		if (LCS[i - 1][j] > LCS[i][j - 1])
		{
			print_LCS(i - 1, j);
		}
		else
		{
			print_LCS(i, j - 1);
		}
	}
}

int main(void)
{
	scanf("%s", string_1);
	scanf("%s", string_2);
	int len_1 = strlen(string_1);
	int len_2 = strlen(string_2);

	for (int i = 0; i < len_1; i++)
	{
		LCS[i][0] = 0;
	}
	for (int j = 0; j < len_2; j++)
	{
		LCS[0][j] = 0;
	}

	for (int i = 1; i <= len_1; i++)
	{
		for (int j = 1; j <= len_2; j++)
		{
			if (string_1[i - 1] == string_2[j - 1])
			{
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			}
			else
			{
				LCS[i][j] = MAX(LCS[i - 1][j], LCS[i][j - 1]);
			}
		}
	}

	printf("%d\n", LCS[len_1][len_2]);
	print_LCS(len_1, len_2);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ