코테 준비용 공부 - LCS 2

LCS 2

이번 문제는 DP에 있어서
유명한 문제 중 하나인
LCS(Longest Common Subsequence)의 연장선이다.
(백준에 실제로 기본적인 LCS문제가 존재한다.)

대부분의 수학문제도, 알고리즘 문제도 그렇듯이
기본 개념을 어떻게 활용시키느냐, 가 초점 아니겠는가?

단순히 세상에 널리 알려진 알고리즘을 주어진 입력에 대해 naive 하게 적용하는 문제들도 있지만, 이렇게 한 발 짝 더 나아간 문제들도 꽤나 많다.

이 문제에서 핵심은 이거다.
LCS야 기본 유형이라 길이 구하는 법은 이제 다들 알지? LCS길이는 알겠고 그거 역추적해봐!

아마도 배낭 문제였던가 어디서 분명 역추적하는 문제를 풀었던 것 같기도 하다.

여러모로 고민하고 고민했지만, 특정 예시에서 계속 막혀서
결국 방법을 좀 찾아봤고, 찾아본 결과
2차원 배열 DP의 맨 마지막 (그러니까 두 문자열 a,b의 사이즈 i,j)에 대해서
a[i]==b[i]일 경우와 그렇지 않을 경우에 대해
i와 j의 값을 계속 조작하면 되는 문제였다!

물론 문자열이 뒤집힌 상태지만, reverse 한번 써 주면
충분히 바로 답을 구할 수 있다.
case는 다음과 같다.

1. a[i]==b[j]일 경우
   -> 값을 저장하고, i=i-1, j=j-1로 진행
2. a[i]!=b[j]일 경우
   1. dp[i][j]==dp[i-1][j]이면 i=i-1
   2. dp[i][j]==dp[i][j-1]이면 j=j-1

같은 식으로 문제를 풀 수 있었다.

사실 처음 lcs의 길이를 구할 때의 방식을 완전히 뒤집은 것 이다.

참 세상은 넓고 나는 부족하다.

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string answer;
int dp[1001][1001];
int main(){
	string s1;
	string s2;
	cin>>s1>>s2;
	for(int i=0;i<=s1.size();i++){
		for(int j=0;j<=s2.size();j++){
			dp[i][j]=0;
		}
	}
	int maxV = 0;
	for(int i=0;i<s1.size();i++){
		for(int j=0;j<s2.size();j++){
			if(s1[i]==s2[j]){
				dp[i+1][j+1]=dp[i][j]+1;
			}
			else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
			maxV=max(maxV,dp[i+1][j+1]);			
		}
	}
	
	if(maxV==0){
		cout<<0;
	}
	else{
		int k = 0;
		int i = s1.size();
		int j = s2.size();
		while(i>0&&j>0){
			if(s1[i-1]==s2[j-1]){
				answer.push_back(s1[i-1]);
				i--;
				j--;
			}
			else{
				if(dp[i][j]==dp[i-1][j]){
					i--;
				}
				else{
					j--;
				}
			}
		}
		reverse(answer.begin(),answer.end());
		cout<<maxV<<'\n'<<answer;
	}
	return 0;
}