[백준/C++] #9251 LCS (DP/LCS)

문제

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

 

구상

사실.. 문제 이름 자체가 LCS여서... 바로 LCS 대입해서 풀었다. 

 

알고리즘

: LCS (Longest Common Subsequence)

 두 수열이나 문자열에서 공통되는 가장 긴 부분수열 혹인 부분 문자열

 중요한건, 공통되는 문자열이 연속적일 필요는 없다!

 

LCS는 2차원 DP 배열을 통해 구할 수 있다. 

 

풀이 + 코드

if (현재 비교하는 문자가 서로 다르다면) 왼쪽, 위쪽 두 개의 값 중 큰 값 저장

else 왼쪽 위 대각선의 값 + 1 저장 

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

string s1, s2;
vector<vector<int>> dp;
/*
9251 LCS
*/
int main() {
  cin >> s1 >> s2;
  s1 = "0" + s1;
  s2 = "0" + s2;

  dp.resize(s2.size(), vector<int>(s1.size()));

  for (int i = 0; i < s2.size(); i++) {
    for (int j = 0; j < s1.size(); j++) {
      if (i == 0 || j == 0) // 테두리는 0으로 초기화
        dp[i][j] = 0;
      else if (s1[j] == s2[i]) // 비교하는 값이 같다면
        dp[i][j] = dp[i-1][j-1] + 1; // 1 증가
      else // 다르다면
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 위, 왼 값의 최댓값 입력
    }
  }
  cout << dp[s2.size()-1][s1.size()-1] << endl; // 맨 마지막 인덱에 저장된 lcs 출력
  return 0;
}