[9252] LCS2 - C++

---

풀이

먼저 내가 썼던 글을 보고 오도록 하자, 그래야 이 문제도 이해할 수 있다!

https://juuuuung.tistory.com/126

[9251]LCS - C++

※위의 글을 읽었다는 가정하에 풀이를 시작하겠다.※

 

최대 공통 문자열의 수를 구하는 알고리즘(LCS)

cin >> A >> B;
  for(int i = 1; i <= A.length(); ++i)
    for(int j = 1; j <= B.length(); ++j)
      dp[i][j] = (A[i-1]==B[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]));

 

그 문자열을 구하는 법

현재 나의 왼쪽(←) , 위(↑)를 검사하며 같으면 그쪽으로 이동

같은 곳이 없다면 왼쪽 위 대각선(↖)으로 이동

 

대각선으로 이동할 때만 스택에 그 문자열 저장

 

이 그림이 시작이다.

stack = [ ]

stack = [K]

 

stack = [K, A]

stack = [K, A, C]

stack = [K, A, C, A]

전체 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

string A, B;
int dp[1002][1002];
int dx[2] = {0, -1};
int dy[2] = {-1, 0};

stack<char> str;

int main(){
   init();
   //입력
   cin >> A >> B;
   
   //LCS
   for(int i = 1; i <= A.length(); ++i)
      for(int j = 1; j <= B.length(); ++j)
         dp[i][j] = (A[i-1]==B[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]));

   int x = A.length(), y = B.length();
   
   //문자열 찾기
   while(dp[x][y] != 0){
   	  //왼쪽 검사
      if(dp[x + dx[0]][y + dy[0]] == dp[x][y]){
         x += dx[0]; y += dy[0];
      }
      //오른쪽 검사
      else if(dp[x + dx[1]][y + dy[1]] == dp[x][y]){
         x += dx[1]; y += dy[1];
      }
      //대각선 스택에 추가
      else{
      	 str.push(A[--x]);--y;
      }
   }
   //길이 출력
   cout << dp[A.length()][B.length()] <<'\n';
   //문자열 출력
   while(!str.empty()){
      cout << str.top();
      str.pop();
   }
  return 0;
}