백준 9252번 LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

 

 

LCS로 길이 구하면 되고

문자열은 실제로 문자가 추가되는 지점에서 더해주면 되는데, 대각선에서 넘어올 때 문자 길이가 1증가하는 것이다.

이미 앞에서 '0'을 붙이고 왔기 때문에 i,j에서 일치할 때 i-1,j-1 길이에서 1만큼 더해주는데 그 더해주는 문자는

i인덱스의 str1 (j인덱스 str2 와 같음) 이다. 따라서 i-1의 문자가 아닌 i 문자 더해주면 끝.

#include <iostream>
#include <string.h>
#include <deque>
#include<queue>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;

int LCS[1001][1001];
int main(void)
{
	string tmp1, tmp2, str1, str2;
	cin >> tmp1 >> tmp2;
	str1 = '0' + tmp1;
	str2 = '0' + tmp2;

	int N = str1.size();
	int M = str2.size();

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!i || !j)
			{
				LCS[i][j] = 0;
			}
			else
			{
				if (str1[i] == str2[j])
				{
					LCS[i][j] = LCS[i - 1][j - 1] + 1;
				}
				else
				{
					LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
				}
			}


		}
	}
	cout  << LCS[N - 1][M - 1] << endl;

	int y = N - 1;
	int x = M - 1;
	string res = "";
	while (LCS[y][x] != 0)
	{
		if (LCS[y][x] == LCS[y - 1][x])
		{
			--y;
		}
		else if (LCS[y][x] == LCS[y][x - 1])
		{
			--x;
		}
		else if (LCS[y][x] - 1 == LCS[y - 1][x - 1])
		{
			res += str1[y];
			--y;
			--x;
		}
	}
	reverse(res.begin(), res.end());
	cout << res << endl;
	
	return 0;
}