baekjoon 30805:사전 순 최대 공통 부분 수열

baekjoon 30805 사전 순 최대 공통 부분 수열

30805번 사전 순 최대 공통 부분 수열

접근

이 문제는 나름 쉽다.
가장 큰 수를 찾아서 그 수 부터 양 수열에서 찾아나가면 된다.
그 다음부턴 그 뒤부터 탐색한다. 탐색 대상은 그전 탐색과 같은 수부터 1씩 줄여나가면 된다.
왜그러냐면 탐색대상보다 큰 수는 이미 전 탐색에서 없다고 나왔으니까 탐색 대상에서 제외됐을 것이다.

코드

#include <iostream>
#include <vector>
#include <array>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  int m; cin >> m;
  vector<int> b(m);
  for(int i = 0; i < m; i++){
    cin >> b[i];
  }
  int a_idx = 0, b_idx = 0;
  vector<int> ans;
  int max = 1;
  for(auto i: a){
    if(i > max){
      max = i;
    }
  }
  for(auto i: b){
    if(i > max){
      max = i;
    }
  }
  int j = max;
  while(j>=1){
    bool a_flag = false, b_flag = false;
    int a_i, b_i;
    for(a_i = a_idx; a_i < n; a_i++){
      if(a[a_i] == j){
        a_flag = true;
        break;
      }
    }
    for(b_i = b_idx; b_i < m; b_i++){
      if(b[b_i] == j){
        b_flag = true;
        break;
      }
    }
    if(a_flag && b_flag){
      ans.push_back(j);
      a_idx = a_i+1;
      b_idx = b_i+1;
      continue;
    }
    else{
      j--;
    }
    
  }
  cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++){
    cout << ans[i] << " ";
  }
  
  return 0;
}

배운 점

그리디 알고리즘이라고 한다.