[백준 9252] LCS 2

[백준 9252] LCS 2

문제 링크

using namespace std;
string s1, s2;
int dp[1004][1004];
string lcs[1004][1004];
void input() {
  cin >> s1 >> s2;
}
void solve() {
  int n = s1.length();
  int m = s2.length();
  string answer = "";

  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      if(s1[i-1] == s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
        lcs[i][j] += lcs[i-1][j-1] + s2[j-1];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if(lcs[i-1][j].length() > lcs[i][j-1].length()) {
          lcs[i][j] = lcs[i-1][j];
        } else lcs[i][j] = lcs[i][j-1];
      }
    }
  }

  cout << dp[n][m] << endl;
  if(dp[n][m]) cout << lcs[n][m] << endl;
}
int main() {

  input();
  solve();

  return 0;
}

• LCS와 거의 똑같은 문제지만, 어떤 문자열이 LCS인지 출력 해야 한다.
• LCS의 길이를 구한 것과 동일하게, string배열을 생성 해서 똑같이 업데이트 해 준다.