백준 17076번 망가진 데이터

문제

택희는 이번 대회에 사용하기 위해 그래프를 몇 개 만들었다.

택희의 그래프 데이터는 항상 아래의 형식을 따른다.

N M U1 V1 U2 V2 U3 V3 ... UM VM

위는 정점이 N개, 간선이 M개인 그래프 데이터로, 모든 Ui, Vi에 대해 1 ≤ Ui, Vi ≤ N을 만족하며, N과 M 뒤에 등장하는 간선 정보(U, V 페어)는 정확히 M개이다. 그 외의 다른 조건은 없다.

택희는 대회에 사용할 모든 그래프를 만들었고, 데이터를 업로드하려던 그 순간! 갑자기 영훈이가 나타나 데이터의 여기저기에 임의의 정수를 몇 개 써 넣어 버렸고, 택희는 순간적인 상황 변화를 받아들이지 못하고 격한 욕설을 내뱉으며 영훈이에게 당장 원래 데이터로 고쳐 두라고 말한 뒤 자리를 떠나 버렸다.

영훈이는 최대한 빠르게 그래프 데이터를 복원해야 한다. 하지만 자신이 어디에 어떤 수를 썼는지 전혀 기억하지 못하는 영훈이는 고민에 빠졌다.

영훈이는 자신이 데이터에 한 일은 수를 임의의 위치에 넣은 것뿐이라는 것을 알기에, 데이터에서 몇 개의 수를 지워 그래프 데이터를 만들려 한다. 즉, 수들의 원래 순서를 유지하면서 수 일부를 지워, 남은 수들이 '올바른 데이터' 가 되도록 하려는 것이다. 이때 '올바른 데이터' 란,

4개 이상의 정수로 이루어져 있고,
택희가 처음 만든 데이터의 형식을 따르며,
택희가 지키려 했던 모든 조건을 지키고 있는 데이터를 의미한다.

영훈이는 그래프를 복원할 방법이 여러 가지라면 기왕이면 노드의 수(N)가 가장 큰 것을, 그러한 것도 여러 가지라면 간선의 수(M)가 가장 큰 것을 복원할 것이다.

현재 데이터의 상태가 주어졌을 때, 영훈이가 복원할 그래프의 노드의 수와 간선의 수를 알아내보도록 하자.

문제풀이

사용한 알고리즘 : segtree

(0) 생각

문제 조건을 만족하는 N, M이 될 수 있는 수를 뒤부터 탐색하면서 찾을 것입니다.

각 탐색 시 조건을 만족하는 N, M이 되기 위해서는,

1. 해당 수가 M이 되기 위해서는 해당 수 뒤에 최소 2*M개의 수가 있어야 합니다.

2. M 앞의 N이 될 수는 M뒤의 2*M 번째로 작은 수 이상이어야 합니다.

( M 뒤에서 무조건 작은 2*M개로 그래프 연결 관계를 생각한다. )

예를 들어 5 5 2 9 8 2 6 12 8 1 5 14 를 살펴보면,

1] 5 5 2 9 8 2 6 12 8 1 5 14 경우

14는 뒤에 적어도 2*14개의 수가 있어야 하는데 없다. (14는 M이 될 수 없다.)

2] 5 5 2 9 8 2 6 12 8 1 5 14 경우

5는 뒤에 적어도 2*5 개의 수가 있어야 하는데 없다. (5는 M이 될 수 없다.)

3] 5 5 2 9 8 2 6 12 8 1 5 14 경우

1은 뒤에 2*1 개의 수가 있으므로 M이 될 수 있다.

1 뒤의 2*1 번째로 작은 수는 14 인데, 1 앞에 14이상의 수가 없다.

(N이 될 수 있는 수가 없다.)

4] 5 5 2 9 8 2 6 12 8 1 5 14 경우

8 뒤에 적어도 2*8개의 수가 있어야 하는데 없다. (8은 M이 될 수 없다.)

5] 5 5 2 9 8 2 6 12 8 1 5 14 경우

12는 뒤에 적어도 2*12개의 수가 있어야 하는데 없다. (12는 M이 될 수 없다.)

6] 5 5 2 9 8 2 6 12 8 1 5 14 경우

6은 뒤에 적어도 2*6개의 수가 있어야 하는데 없다. (6은 M이 될 수 없다.)

7] 5 5 2 9 8 2 6 12 8 1 5 14 경우

2는 뒤에 2*2 개 이상의 수가 있으므로 M이 될 수 있다.

2 뒤에서 2*2번째 작은 수는 8이다.

9는 8 이상이므로 N이 될 수 있다.

따라서 N, M = 9, 2 로 찾을 수 있다.

이때 그래프는 9 2 1 5 6 8 이라고 생각 가능합니다. (혹은 9 2 6 8 1 5)

위 과정을 뒤에서부터 두번째 수까지 반복합니다.

( M이 가능한 수부터 탐색하므로 적어도 앞에 하나는 N이 될 수가 있어야 합니다.)

(1) 코드 25~38

뒤에서부터 탐색 하면서 보게 되는 수들을 차례로 segtree로 업데이트 해줍니다.

이렇게 되면 i번째 탐색시, i+1~끝까지 수들은 segtree에 쌓여있습니다.

i번째 수 탐색 시 i 뒤에서 2*(i번째 수) 번째로 작은 수를 찾게 해줍니다.

(2) 코드 7~24

i번째 탐색 시, i번째 앞에 있는 수중 가장 큰 수를 찾는 segtree입니다.

(3) 코드 52~67

뒤에서부터 차례로 탐색합니다.

i번째 수 탐색 시, i 뒤에 2*(i번째 수) 만큼 수가 있는지 판단하고,

이들 중 2*(i번째 수) 번째로 작은 수를 찾고,

i앞에 '2*(i번째 수) 번째로 작은 수' 이상의 수가 있는지 확인합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1 << 18;

	int K, arr[MAX];

	int segtree[2 * MAX];
	void update(int x, int num) {
	segtree[x] = num;
	while (x / 2 > 0) {
	x /= 2;
	segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
	}
	}
	// 0이상 ~ To미만 가장 큰 수
	int Maxi(int To, int idx = 1, int s = 0, int e = MAX - 1) {

	if (e < To) return segtree[idx];
	if (s >= To) return 0;

	int mid = (s + e) / 2;
	int ret = max(Maxi(To, 2 * idx, s, mid), Maxi(To, 2 * idx + 1, mid + 1, e));
	return ret;
	}

	int numtree[2 * MAX]; // num[MAX+x] : x 값을 갖는 애들 수
	void num_update(int x) {
	while (x > 0) {
	numtree[x]++;
	x /= 2;
	}
	}
	// num번째로 작은 수 찾기
	int Mini(int num, int idx = 1, int s = 0, int e = MAX - 1) {
	if (idx >= MAX) return s;

	int mid = (s + e) / 2;
	if (numtree[2 * idx] >= num) return Mini(num, 2 * idx, s, mid);
	else return Mini(num - numtree[2 * idx], 2 * idx + 1, mid + 1, e);
	}

	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> K;
	for (int i = 0; i < K; ++i) {
	cin >> arr[i];
	update(MAX + i, arr[i]);
	}
	int ans_N = -1;
	int ans_M = -1;

	for (int i = K - 1; i > 0; i--) { // k-1에서 1까지 (0 전까지) 볼꺼임
	int now = arr[i]; // i번째 수
	int need = 2 * now;

	if (numtree[1] >= need) {
	int befo = Maxi(i); // M 앞의 가장 큰 수
	int afto = Mini(need); // M 뒤의 2*M번째로 작은 수
	if (befo >= afto) {
	if ((ans_N < befo) \|\| (ans_N == befo && ans_M < now)) {
	ans_N = befo;
	ans_M = now;
	}
	}
	}
	num_update(MAX + now);
	}
	if (ans_N == -1) cout << -1 << '\n';
	else cout << ans_N << " " << ans_M << '\n';

	return 0;
	}

view raw BOJ 17076.cpp hosted with ❤ by GitHub

검색

마포 코딩박 C++ Algorithm