[BOJ 2787 // C++] 흔한 수열 문제

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2787번 문제인 흔한 수열 문제이다.
문제는 아래 링크를 확인하자.

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

2787번: 흔한 수열 문제

문제에서 주어지는 1 x y v, 2 x y v의 쿼리들을 종합하면 다음과 같은 두 가지 정보를 얻을 수 있다. (N이 충분히 작으므로, 해당 정보들의 처리는 O(N^2)에 구현해도 상관없다.)

 

(1) 주어진 수열의 i번째 원소에 들어갈 수 있는 수의 범위

(2) i라는 수가 들어갈 수 있는 수열의 인덱스의 범위

 

(2)에 대해 보충설명하면, 문제에서 주어지는 쿼리는 수열의 [x,y] 범위에는 v라는 값이 무조건 존재해야 함을 내포하고 있어 해당 정보 또한 관리해야 한다. 특히, 각 수는 배열에 정확히 한 번씩만 등장해야하므로 [x,y]의 범위 밖에서는 v가 등장할 수 없다는 점을 놓치지 말자.

 

위의 두 정보를 이용해 수열의 각 인덱스에 들어갈 수 있는 수의 후보를 추려내고, 수열의 인덱스와 실제 수를 매칭시켜 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#define NODE 201
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
vector<int> G[NODE];
int visited[NODE];
int matching[NODE];

int bpfunc(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bpfunc(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

int bipartitematching() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ret += bpfunc(i);
	}

	return ret;
}

int mx[201];
int mn[201];
int ans[201];
int rangedmx[201];
int rangedmn[201];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int M; cin >> N >> M;
	for (int i = 1; i <= N; i++) mx[i] = N, mn[i] = 1, rangedmx[i] = N, rangedmn[i] = 1;

	while (M--) {
		int q, x, y, v; cin >> q >> x >> y >> v;
		if (q == 1) {
			for (int i = x; i <= y; i++) mx[i] = min(mx[i], v);
		}
		else {
			for (int i = x; i <= y; i++) mn[i] = max(mn[i], v);
		}
		rangedmx[v] = min(rangedmx[v], y);
		rangedmn[v] = max(rangedmn[v], x);
	}
	for (int n = 1; n <= N; n++) {
		for (int i = mn[n]; i <= mx[n]; i++) {
			if (rangedmn[i] <= n && n <= rangedmx[i]) G[n].emplace_back(i);
		}
	}

	if (bipartitematching() < N) cout << -1;
	else {
		for (int i = 1; i <= N; i++) {
			ans[matching[i]] = i;
		}
		for (int i = 1; i <= N; i++) cout << ans[i] << ' ';
	}
}