[백준 2336번] 굉장한 학생

---

2336번: 굉장한 학생

---

 

목차

• 사전 지식
• 문제 접근

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)

 

 

 

문제 접근

먼저, 대단한 학생과 굉장한 학생의 정의를 정확히 이해해야 한다.

학생 A의 등수가 $(a_1, a_2, a_3)$이고 B의 등수가 $(b_1, b_2, b_3)$일 때, $\small{a_1 < b_1} \large{,}$ $\small{a_2 < b_2} \large{,}$ $\small{a_3 < b_3}$를 만족하면 A는 B보다 대단한 학생이다.
만약에, A보다 대단한 학생이 없다면 A는 굉장한 학생이다.

 

여기서, 알 수 있는 사실은 A가 B보다 대단하다면 B는 굉장한 학생이 아니라는 점이다.

즉, B보다 대단한 학생이 한 명이라도 있으면 B는 굉장한 학생이 아니라고 확정 지을 수 있다는 것이다!

 

위의 사실을 잘 이용할 수 있도록 한 과목을 기준으로 정렬을 해보자.

(아래의 배열은 가로(index)가 학생들, 세로가 과목들에 대응한다. 이는 문제의 입력 형식과 다르다는 점을 주의하자.)

과목1을 기준으로 정렬

 

위 배열에서 과목1에 대해,  $i < j \ $라면 $a_i < a_j \ $를 항상 만족한다는 것을 알 수 있다.

즉, $i$번째 학생이 굉장한 학생임을 알고 싶을 때, $j$번째 학생을 살펴볼 이유가 없다. (이미 과목1에서 등수가 더 좋기 때문)

등수가 더 좋다는 말은 등수가 더 작다는 의미이다. ( ex) 1등이 3등보다 좋다(작다) )

 

따라서, 0번째 학생은 항상 굉장한 학생이며,

1번째 학생은 0번째 학생만 살펴보면 자신이 굉장한 학생인지를 알 수 있고,

2번째 학생은 0~1번째 학생만 살펴보면 자신이 굉장한 학생인지를 알 수 있고,

3번째 학생은 0~2번째 학생만 살펴보면 자신이 굉장한 학생인지를 알 수 있다.

...

N번째 학생은 0~N-1번째 학생만 살펴보면 자신이 굉장한 학생인지를 알 수 있다.

 

만약, 과목의 종류가 2개라면?

2차원 배열 arr

과목의 개수가 2개라면 위의 배열을 한 번의 탐색만으로 답을 구할 수 있다.

인덱스가 $j$인 원소를 살펴볼 때, 인덱스가 $i < j$인 $i$에 대해 $\small{arr[1][i] < arr[1][j] \ }$을 만족하는 $i$가 존재하는지 살펴보면 된다.

이는 현재 살펴본 과목2의 최소값(가장 좋은 등수)을 저장하면 바로바로 확인할 수 있다.

 

따라서, 과목의 종류가 2개라면 굉장한 학생의 수를 $O(N)$만에 구할 수 있다.

 

그렇다면, 과목의 종류가 3개라면?

2차원 배열 arr

과목의 종류가 2개였을 때의 풀이와 비슷하게 접근해 보자. 인덱스가 $j$인 원소를 살펴볼 때,

인덱스가 $i < j$인 $i$에 대해 $\small{arr[1][i] < arr[1][j]}$과 $\small{arr[2][i] < arr[2][j]}$을 만족하는 $i$가 존재하는지 살펴보면 된다.

세그먼트 트리를 이용하면 이를 $O(\log N)$시간 안에 구할 수 있다.

 

세그먼트 트리에서 리프 노드의 인덱스를 $arr[1]$의 값으로, 그리고 여기에 들어간 값은 $arr[2]$의 값으로 구성하면 된다.

즉, 세그먼트 트리의 인덱스는 2번째 과목의 등수를 의미하며, 거기에 들어간 값은 그 학생의 3번째 등수를 의미하게 된다.

 

이렇게 세그먼트 트리를 구성하면 query(0, rank2 - 1)를 통해서 다음과 같은 수행을 할 수 있다.

• 2번째 과목 점수가 rank2보다 작은 학생들을 접근할 수 있다.
• rank2보다 작은 학생들 중에서 가장 좋은(작은) 3번째 과목 등수를 반환한다.

세그먼트 트리는 완성된 상태에서 시작하는 것이 아니며 각 학생들을 둘러보며 갱신된다는 점을 주의하자!

 

	// BOJ 2336
	// Sort & SegTree
	#include <bits/stdc++.h>
	using namespace std;
	int sz;
	vector<int> tree;
	void update(int idx, int x) {
	idx += sz;
	tree[idx] = x;
	while (idx /= 2) tree[idx] = min(tree[2*idx], tree[2*idx+1]);
	}
	int query(int a, int b) {
	a += sz; b += sz;
	int ret = int(5e5);
	while (a <= b) {
	if (a%2 == 1) ret = min(ret, tree[a++]);
	if (b%2 == 0) ret = min(ret, tree[b--]);
	a /= 2; b /= 2;
	}
	return ret;
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N; cin >> N;
	vector<array<int, 3>> arr(N); // arr[N][3]
	for (int i=0; i<3; i++) {
	for (int j=1; j<=N; j++) {
	int student; cin >> student;
	arr[student-1][i] = j;
	}
	}
	sort(arr.begin(), arr.end());
	sz = (1 << (int)ceil(log2(int(5e5))));
	tree.assign(2*sz, int(5e5));
	int res = N;
	for (auto &[rank1, rank2, rank3] : arr) {
	if (query(0, rank2-1) < rank3) res--;
	update(rank2, rank3);
	}
	cout << res << '\n';
	return 0;
	}

view raw 2336.cpp hosted with ❤ by GitHub