(9252) LCS 2

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 4번째

 

 

 

DP 갱신의 특수성 때문에 반대로 from 없이 dp배열만으로도 역추적이 가능한 문제.

문자가 겹쳐야 dp값이 갱신되므로 dp[x][y]에서 dp[x+1][y+1]로 넘어갈 때는 값이 1 증가하고, dp[x+1][y]나 dp[x][y+1]로 넘어갈 때는 값이 증가하지 않는 지점이 생긴다. 이 지점의 문자를 가져오면 된다.

 

 

 

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

int main() 
{
  string s1, s2;
  
  cin >> s1 >> s2;
  
  vector dp(s1.length()+1, vector<int> (s2.length()+1));
  
  for(int i=1;i<=s1.length();i++){
    for(int j=1;j<=s2.length();j++){
      dp[i][j]= max(dp[i-1][j], dp[i][j-1]);
      if(s1[i-1]==s2[j-1])  dp[i][j]= max(dp[i][j], dp[i-1][j-1]+1);
    }
  }
  
  int x= s1.length(), y= s2.length();
  string res;
  
  cout << dp[x][y] << "\n";
  
  while(x&&y){
    if(dp[x-1][y]==dp[x][y]){
      x--;
    }else if(dp[x][y-1]==dp[x][y]){
      y--;
    }else{
      x--;
      y--;
      res= s1[x]+res;
    }
  }
  
  cout << res;
  
  return 0;
}