[C/C++][DP] 백준 9252번: LCS 2

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

두 문자열을 각각 가로축, 세로축으로 두고 문자열이 같은 부분에서 문자열 길이를 담은 DP배열에 +1해준다.

그 다음 인덱스는 전 단계에서 얻어진 DP배열에서 큰 값을 얻는다.

점화식

a[i] == b[i] 일 때 dp[i][j] = dp[i-1][j-1] + 1

그렇지 않을 때, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

LCS 문자열을 구하는 과정은 점화식을 거슬러 올라가면 된다.

a[i] == b[i] 일 때 dp[i-1][j-1] 출력 후 이동

그렇지 않을 때, dp[i][j-1] 과 dp[i-1][j] 중에 큰 값 출력 이동

문자열을 역추적 해서 올라갔으므로 재귀 호출을 먼저하여 출력을 나중에 하면 순방향 문자열이 나온다.

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1002][1002];
string a;
string b;

void dprint(int i,int j){
  if(dp[i][j]==0) return ;

  if(a[i-1]==b[j-1]){
    dprint(i-1,j-1);
    cout << a[i-1];
  }
  else{
    if(dp[i-1][j]>dp[i][j-1]){
      dprint(i-1,j);
    }
    else dprint(i,j-1);
  }
}
int main(){
  cout.tie(NULL);
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  //

  cin >> a >> b;

  for(int i=0;i<a.size();++i){
    for(int j=0;j<b.size();++j){
      dp[i][j]=0;
    }
  }
  for(int i=0;a[i];++i){
    for(int j=0;b[j];++j){
      if(a[i]==b[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]);
    }
  }
  cout<<dp[a.size()][b.size()]<<'\n';
  dprint(a.size(),b.size());
  return 0;
}