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

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

 

코드

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

typedef pair<int, int> pi;
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

bool cmp(pi a, pi b) {
	if (a.first == b.first) return a.second < b.second;
	return a.first > b.first;
}

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

	vector<int> ans;
	sort(a.begin(), a.end(), cmp);
	sort(b.begin(), b.end(), cmp);

	int idxa = 0, idxb = 0, limita=0, limitb=0;
	while (idxa < n && idxb < m) {
		if (a[idxa].first == b[idxb].first) {
			if (limita > a[idxa].second) idxa++;
			else if (limitb > b[idxb].second) idxb++;
			else {
				limita = a[idxa].second;
				limitb = b[idxb].second;
				ans.push_back(a[idxa].first);
				idxa++;
				idxb++;
			}
		}
		else if (a[idxa].first > b[idxb].first) idxa++;
		else idxb++;
	}

	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	return 0;
}

코드 설명

문제를 요약하면 두 배열의 공통된 최댓값을 찾은 후, 해당 최댓값 이후 위치부터 다시 최댓값을 찾는 것을 반복하면 된다. 따라서 값과 인덱스를 모두 저장한 후 정렬해서 조건에 맞게 포인터를 이동시켜주면 된다.

 

A와 B를 저장할 때는 값과 인덱스를 모두 저장해준 후 값 내림차순으로, 값이 같을 때는 인덱스 오름차순이 되도록 정렬해준다. 값이 같을 때는 인덱스 오름차순으로 정렬하는 이유는 같은 값이 여러 번 등장할 때 먼저 등장한 것을 사용해야 놓치는 구간이 없어지기 때문이다.

 

idxa와 idxb는 A와 B의 포인터로 사용하고, limita, limitb는 가장 마지막으로 사용한 최댓값의 인덱스값을 저장하는 데 이용한다. A와 B의 원소값이 같으면서 모두 이전 최댓값 이후에서 등장했을 경우에는 이를 ans 벡터에 넣어주고 idxa와 idxb의 값을 모두 같이 증가시켜준다. 그렇지 않을 경우에는 값이 더 큰 쪽의 벡터 인덱스를 증가시켜준다.

 

 

하나의 벡터라도 끝에 도달했다면 반복문을 종료하고 ans의 크기를 출력하고, 반복문으로 원소를 출력한다.

 

느낀 점

문제 제목만 봤을 때는 가장 긴  증가하는 부분 수열 계열 문제처럼 DP로 풀어야 할 줄 알았다. 내용을 읽어보니 그리디하게 풀면 되는 문제였다. 그래서 바로 흐름을 잡아서 풀었다.