백준 9252(LCS2)

https://www.acmicpc.net/problem/9252

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 LCS 최장공통부분수열의 길이와 그 수열을 출력하는 문제입니다.

 

두 문자열이 있을때 공통으로 존재하는 가장긴 수열을 구하는 것입니다.

 

따라서 dp를 이용하여 이전까지의 길이를 바탕으로 비교해나가는 방식을 이용하여야 합니다.

 

두 문자열이 있을때 각 문자열의 길이를 1씩 늘려가며 현재 비교하는 위치의 두문자열의 문자가 동일한 경우 dp의 길이를 증가시켜주는 방식을 이용하여야 합니다.

 

두문자열을 잡고 직접 표를 그려보시면 이해가 쉬울 것입니다.

 

결론적으로 if(str1[i-1] == str2[j-1])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

이러한 점화식이 나오게 되는데 두 문자가 동일한 상태라면 두문자를 각각 포함하지 않은 dp의 값에서 1을 증가시켜주고

 

현재 두문자가 동일하지 않은 상태라면 dp에는 각각 첫번째 문자와 두번째 문자를 제거한 상태의 dp값중 큰값을 가지게 됩니다. 따라서 최종 끝까지 비교하게 되면 두문자열의 최장부분수열의 길이를 구할 수 있습니다.

 

다음으로 최장부분수열을 출력하기 위해서는 dp배열의 값이 1 줄어드는 최초의 시점을 주목해야 합니다. 따라서 처음에 최장길이에 해당하는 길이에서 왼쪽으로 가며 길이가 줄어들때까지 문자를 하나씩 줄여갑니다. 그다음은 윗부분을 확인하여 길이가 줄어들때까지 문자를 줄여나간뒤 왼쪽과 위가 모두 줄어든 상태라면 현재그위치의 문자가 부분수열에 해당하는 문자가 됩니다. 따라서 스택에 집어넣고 대각선 왼쪽방향으로 이동하며 계속해서 길이가 0일때까지 탐색을 진행해 주면 최종 문자까지 출력할 수 있게 됩니다.

 

꽤나 이해하기 어려웠던 알고리즘 입니다. 두문자열을 예로두고 문자하나 하나씩 비교해가며 표를 그리는게 이해하기 쉬울 것 같습니다.

 

다음은 코드입니다.

 

 #include <iostream>
#include <string>
#include <stack>

using namespace std;

/*
	dp[0][0] 부터 인덱스에 0이 있는 부분은 0으로 초기화 해놔야함.
	실제 저장은 dp[1][1] 부터 - > 첫번째 문자와 첫번째 문자 비교 
	dp[1][2] -> 첫번째 문자와 두번째문자열의 첫번째 두번째 문자의 부분수열 길이 
	
	문자의 출력은 왼쪽과 윗쪽 모두 다른경우 대각선으로 이동하며 출력해주면 됨.
	왼쪽부터 간다음 위쪽 확인 한다음 모두 다르면 대각선 확인 
*/

int dp[1001][1001];

int main(void) {
	string str1;
	string str2;
	stack<char> s;
	cin>> str1 >> str2;
	
	int len1 = str1.size();
	int len2 = str2.size();

	for(int i = 1; i <= len1; i++)
		for(int j = 1; j <= len2; j++) {
			if(str1[i-1] == str2[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}

	while(dp[len1][len2] != 0){
			if(dp[len1][len2] == dp[len1][len2-1]) //왼쪽 비교
				len2--;
			else if(dp[len1][len2] == dp[len1-1][len2]) //윗쪽 비교
				len1--;
			else if(dp[len1][len2] - 1 == dp[len1-1][len2-1]) {
				s.push(str1[len1-1]);
				len1--;
				len2--;
			}
		}

	cout<<dp[str1.size()][str2.size()]<<'\n';

	while(!s.empty()) {
		cout<<s.top();
		s.pop();
	}
	return 0;
}