[백준 30805번] 사전 순 최대 공통 부분 수열 (C++)

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

수열 A와 수열 B에서 공통으로 가장 큰 수를 찾고 그 수를 ans벡터에 넣어주는 식으로 최대 공통 수열을 찾았다.

여기서 수열 A와 B의 공통으로 가장 큰 수를 찾았으면 각 수열에서 공통으로 가장 큰 수의 인덱스보다 작은 인덱스 숫자들은 최대 공통 부분 수열의 원소가 될 수 없으므로 pop해준다.

위의 방식을 한쪽 수열의 벡터의 크기가 0이 될때까지 반복한다. 그럼 최종 ans벡터 수열이 사전 순 최대 공통 부분 수열이 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\n"

using namespace std;

int main() {
	int n,m,num;
	vector<int> a;
	vector<int> b;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> num;
		a.push_back(num);
	}
	cin >> m;
	for(int i = 0; i < m; i++){
		cin >> num;
		b.push_back(num);
	}

	bool flag = true;
	vector<int> ans;
	int max_a, a_idx, max_b, b_idx;
	while(true){
    	//각 수열의 최대 공통 값을 찾음
		while(true){
			if(a.size() == 0 || b.size() == 0){
				flag = false;
				break;
			}
			max_a = *max_element(a.begin(), a.end());
			a_idx = max_element(a.begin(),a.end())-a.begin();
			max_b = *max_element(b.begin(), b.end());
			b_idx = max_element(b.begin(), b.end())-b.begin();
			if(max_a == max_b) break;
			else if(max_a > max_b)	a.erase(a.begin()+a_idx);
			else b.erase(b.begin()+b_idx);
		}
		if(!flag) break;
        
        //최댓값을 ans벡터에 push
		ans.push_back(max_a);
        
        //최댓값 보다 작은 인덱스의 값들을 제거
		int tmp = 0;
		for(int i = a_idx+1; i < a.size(); i++){
			a[tmp] = a[i];
			tmp++;
		}
		for(int i = 0; i < a_idx+1; i++){
			a.pop_back();
		}
		tmp = 0;
		for(int i = b_idx+1; i < b.size(); i++){
			b[tmp] = b[i];
			tmp++;
		}
		for(int i = 0; i < b_idx+1; i++){
			b.pop_back();
		}
	}
	
	if(!ans.empty()){
		cout << ans.size() << endl;
		for(auto v:ans) cout << v << " ";
	}else cout << 0;

}