baekjoon 9252:LCS 2

baekjoon 9252 LCS 2

9252번 LCS 2

접근

LCS(Longest Common Subsequence)는 유명한 dp문제이다. 나도 예전에 풀어본 적 있을 것이다.
하지만 이 문제는 길이 뿐 만 아니라 그 subsequence를 복원해야 한다는 차이점이 있다.
이는 dp하면서 만든 cache 2차원 배열을 통해 추적해 나가면 된다.
dp(y, x)에 3가지가 관여한다.
dp(y+1, x), dp(y, x+1), dp(y+1, x+1)이렇게 3가지다.
dp(y, x)가

1. dp(y+1, x)과 같으면, s1[y-1]무시하라는 것이고
2. dp(y, x+1)과 같으면, s2[x-1]무시하라는 것이고
3. dp(y+1, x+1)보다 1크면 s1[y-1] == s2[x-1]이니 이 character를 string에 추가해야한다.

코드

//9252
#include <iostream>
#include <vector>
#include <array>
using namespace std;
array<array<int, 1002>, 1002> cache;
int dp(int i, int j);
int n, m;
string s1, s2;
string ans;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> s1 >> s2;
  n = s1.size();
  m = s2.size();
  for(auto& i : cache){
    for(auto& j : i){
      j = -1;
    }
  }
  cout << dp(1, 1) << "\n";
  // for(int i = 1; i <= n; i++){
  //   for(int j = 1; j <= m+1; j++){
  //     cout << cache[i][j] << " ";
  //   }
  //   cout << "\n";
  // }
  int y = 1; int x = 1;
  while(dp(y, x) != 0){
    int curr = dp(y, x);
    if(curr == dp(y+1, x)){
      y++;
    }
    else if(curr == dp(y, x+1)){
      x++;
    }
    else if(curr - dp(y+1, x+1) == 1){
      ans += s1[y-1];
      y++; x++;
    }
  }
  if(dp(1, 1) != 0){
    cout << ans;
  }

  return 0;
}
int dp(int i, int j){
  if(i > n || j > m) return 0;
  int& ret = cache[i][j];
  if(ret != -1) return ret;
  if(s1[i-1] == s2[j-1]) {
    return ret = dp(i+1, j+1) + 1;
  }
  return ret = max(dp(i+1, j), dp(i, j+1));
}

배운 점

dp에서 답 복원하는 방법을 배웠다.