[DP] 9251번 - LCS(45일차)

#include <iostream>
//memset 사용
#include <cstring>
//max, max_element 사용
#include <algorithm>
using namespace std;

int main(){
  //두 문자열 입력
  string l1;
  string l2;

  cin >> l1;
  cin >> l2;

  //두 문자열 길이 입력
  int n = l1.size();
  int m = l2.size();

  //2차원 배열 dp 동적 할당
  int ** dp = new int *[n+1];
  for (int i=0; i<n+1; i++){
    dp[i] = new int[m+1];
    memset(dp[i], 0, sizeof(int)*(m+1));
  }

  //첫문자부터 끝까지
  for(int i=1; i<n+1; i++){
    for(int j=1; j<m+1; j++){
      //l1과 l2의 문자가 같을 때
      if(l1[i-1] == l2[j-1]){
        //l1의 직전&l2의 현재, l1의 현재&l2의 직전, l1의 직전&l2의 직전+1 중 가장 큰 길이를 저장
        dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1});
      }
      //l1과 l2의 문자가 다를 때 
      else{
        //l1의 직전&l2의 현재, l1의 현재&l2의 직전, l1의 직전&l2의 직전 중 가장 큰 길이를 저장
        dp[i][j] = max({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]});
      }
    }
  }
  //마지막까지 탐색 이후 가장 긴 길이 출력
  cout << dp[n][m];
}