[BOJ] 9252 - LCS 2

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

BOJ - LCS 2

문제 유형: LCS(Longest Common Subsequence), 다이나믹 프로그래밍, 문자열처리

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 256MB

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

풀이

dp[i][j] = 첫 문자열의 i-1인덱스와 두 번째 문자열의 j-1번째 인덱스를 읽고 난 뒤의 LCS길이로 한다.

dp[0][*]과 dp[*][0]은 빈 문자열과의 비교로, 0이다.

s1[i-1] == s2[j-1]가 같다면 dp[i][j] = dp[i-1][j-1] + 1이다.

그러나 다르다면, dp[i-1][j]와 dp[i][j-1]중 더 긴 길이로 한다.

 

이제, dp[n][m]에는 s1과 s2의 LCS의 길이가 저장되어있다.

이제, 역추적으로 i = n, j = m부터 시작한다.

s1[i-1]랑 s2[j-1]가 같다면, 문자열에 문자를 추가하고 i와 j 둘다 1씩 줄인다.

아니라면, dp[i-1][j]나 dp[i][j-1]중에서 더 긴 쪽으로 i나 j 둘 중 하나만 1씩 줄인다.

이렇게 두 인덱스 중 다시 0으로 돌아올때까지 한다.

 

이러면, 문자열에는 LCS의 역문자열이 남아있다.

LCS를 뒤집어서 출력한다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
string s1, s2;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> s1 >> s2;
  n = s1.size();
  m = s2.size();

  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  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;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  cout << dp[n][m] << "\n";

  int i = n, j = m;
  string lcs = "";
  while (i > 0 && j > 0) {
    if (s1[i - 1] == s2[j - 1]) {
      lcs += s1[i - 1];
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  reverse(lcs.begin(), lcs.end());
  cout << lcs << "\n";

  return 0;
}