9252번: LCS 2

Memo

• LCS 길이가 가장 긴 맨 마지막 부분 부터 시작
• LCS의 규칙이 탐색하고 있는 각 문자들이 같은 경우 왼쪽 대각선 부분에 1을 더하고, 그렇지 않은 경우 max(위, 왼쪽) 인 것을 고려하여, 두 문자가 같아질 때 숫자가 가장 큰 곳을 찾아내는 함수를 호출하고 호출이 끝난 후에 출력을 하는 방법을 생각해 냄.
• 탐색하고 있는 곳의 윗 쪽 부분이랑 크기가 같으면 위로 이동, 왼쪽 부분과 크기가 같으면 이동. 만약 왼쪽 부분의 값이 현재 위치보다 작으면 그 곳이 바로 두 문자가 같아진 부분 중에서 가장 큰 값이므로 dfs 함수를 호출 한 후에 출력.
• 상당히 어려웠음.

Code

제출 날짜

2021/03/12

메모리

6000 KB

시간

4 ms

#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\\n"

std::string a, b;
int up, left;
std::vector<std::vector<int> >LCS;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> a;
	std::cin >> b;
	LCS.resize(b.size() + 1, std::vector<int>(a.size() + 1));
}

void solve()
{
	for (size_t i = 1 ; i <= b.size() ; i++)
		for (size_t j = 1 ; j <= a.size() ; j++)
		{
			if (a[j - 1] == b[i - 1])
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			else
				LCS[i][j] = std::max(LCS[i][j - 1] , LCS[i - 1][j]);
		}
}

void dfs(int b_i, int a_i, int val)
{
	if (b_i <= 0 || a_i <= 0 || val == 0)
		return ;
	up = LCS[b_i - 1][a_i];
	left = LCS[b_i][a_i - 1];
	if (up == val)
		dfs(b_i - 1, a_i, up);
	else if (left == val)
		dfs(b_i, a_i - 1, left);
	else
	{
		dfs(b_i, a_i - 1, left);
		std::cout << b[b_i - 1];
	}
}

void print_val()
{
	std::cout << LCS[b.size()][a.size()] << endl;
	dfs(b.size(), a.size(), LCS[b.size()][a.size()]);
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}