1R/2016 09 17

오늘의 문제

• 2

참가자

• 박인서

코드

박인서

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

int lcs[1001][1001] = { 0, };
char len1[1001] = { 0, }, len2[1001] = { 0, };

int main()
{
	//입력
	std::cin >> len1 >> len2;
	
	//lcs 탐색
	int n = strlen(len1), m = strlen(len2);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (len1[i - 1] == len2[j - 1])
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
			else
				lcs[i][j] = std::max(lcs[i][j - 1], lcs[i - 1][j]);
		}
	}

	//lcs 길이 출력
	std::cout << lcs[n][m] << std::endl;
	std::vector<char> res;
	int x = n - 1, y = m - 1;
	
	//경로 되추적
	while (x >= 0 && y >= 0)
	{
		if (len1[x] == len2[y]) {
			res.push_back(len1[x]);
			x--, y--;
		}
		else lcs[x + 1][y] >= lcs[x][y + 1] ? y-- : x--;
	}
	
	//lcs 출력
	std::reverse(res.begin(), res.end());
	for (int i = 0; i < res.size(); i++) std::cout << res[i];
	
	return 0;
}

아이디어

박인서

• 설명으로 대신합니다.