ghdic

ghdic

Don’t try to show off, just be yourself and do what you enjoy doing.

백준 2336 굉장한 학생 풀이

4 분 소요

문제

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

&Title
2336번 - 굉장한 학생

&Question
N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 
학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 
같은 등수의 학생이 한 명도 없도록 성적을 매겼다.A라는 학생이 
B라는 학생보다 세 번의 시험에서 모두 성적이 좋다면, A가 
B보다 '대단하다'고 한다. 또, C라는 학생보다 '대단한' 학생이 한 
명도 없으면, C를 '굉장하다'고 한다.세 번의 시험에서 각 학생의 
성적이 주어졌을 때, '굉장한' 학생의 수를 구하는 프로그램을 작성하시오. 


&Input
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 
다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 
학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. 


&Output
첫째 줄에 '굉장한' 학생의 수를 출력한다. 

&Example
-input
10
2 5 3 8 10 7 1 6 9 4
1 2 3 4 5 6 7 8 9 10
3 8 7 10 5 4 1 2 6 9

-output
4

요약

  • n명의 학생의 세번의 시험에 대한 순위가 주어진다.
  • A가 B보다 세번의 시험 성적이 더 좋다면 A가 B보다 대단하다라고 한다.
  • 만약 C라는 학생에게 대단한 학생이 한명도 없으면 C를 굉장하다라고 한다.
  • 굉장한 학생의 수를 구하시오.

접근

  • 먼저 첫번째 시험은 정렬을 통해 순위를 판별 할 수 있다.
  • 남은건 두번째, 세번째 시험인데, 이걸 세그먼트 트리를 이용해서 판별한다.
  • 세그 노드인덱스를 두번째시험, 세그 노드의 값을 세번째 시험이라고 두고 구현한다.

풀이

  1. 세그는 평범한 min세그를 구현해준다. 왜냐면 등수는 낮을수록 잘하는거니깐 
     int update(int index, int target, int value, int start, int end) {
     if (target < start || target > end)
         return tree[index];
     if (start == end)
         return tree[index] = value;
     else {
         int mid = (start + end) / 2;
         return tree[index] = min(update(index * 2, target, value, start, mid),
             update(index * 2 + 1, target, value, mid + 1, end));
     }
 }

 int query(int index, int left, int right, int start, int end) {
     if (left > end || right < start)
         return INF;
     if (left <= start && end <= right)
         return tree[index];
     int mid = (start + end) / 2;
     return min(query(index * 2, left, right, start, mid),
         query(index * 2 + 1, left, right, mid + 1, end));
 }
  2. 먼저 세 시험에 대한 값을 입력받고 정렬해준다. 우리는 최소세그를 이용할것이기 때문에 트리의 값을 최대로 다 초기화해준다. 
     for (int i = 0; i < 3; ++i) {
     for (int j = 1; j <= n; ++j) {
         cin >> t;
         score[t][i] = j; // 해당 학생의 등수 적어줌
     }
 }
 sort(score.begin(), score.end());
 fill(&tree[0], &tree[n * 4], INF);
  3. 이제 두번째 시험과 세번째 시험의 순위를 비교해주는데, 1~두번째 시험 등수에 대한 쿼리를 날려 자기보다 세번째 점수가 높은 녀석이 있는지 찾는다. 이 쿼리가 의미하는것은 나보다 두번째 시험 점수가 높은 애들 중 세번째 시험 점수가 제일 높은애의 등수를 쿼리하는 것이다. 즉 아직 자기보다 첫번째 시험 성적이 낮을 수록 두번째 시험 성적이 트리에 업데이트가 늦게 되기 때문에 두번째 시험 성적에 대한 순위 결정이 자연스럽게 이루어지는 것이다. 즉 이러한 조건을 다 만족하면 해당 학생은 굉장한 학생이 되는것이다. 
     int res = 0;
 for (int i = 1; i <= n; ++i) {
     // 첫번째 시험 순서대로 정렬했으니 순서대로 비교(뒤에 있으면 늦게 업데이트되므로 두번째, 세번째만 비교해주면됨)
     // 쿼리로 두번째 시험의 1~score[i][1]등의 최소 세번째 시험 등수를 받아옴
     if (query(1, 1, score[i][1], 1, n) > score[i][2])
         ++res;
     // 두번째 시험 등수에 세번째 시험 등수를 업데이트해줌(1~score[i][1] 쿼리 던질꺼기 때문에)
     update(1, score[i][1], score[i][2], 1, n);
 }

소스

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int MAXN = 500001;
const int INF = 1e9;

int n;
vector<vector<int>> score;
int tree[MAXN * 4];

int update(int index, int target, int value, int start, int end) {
	if (target < start || target > end)
		return tree[index];
	if (start == end)
		return tree[index] = value;
	else {
		int mid = (start + end) / 2;
		return tree[index] = min(update(index * 2, target, value, start, mid),
			update(index * 2 + 1, target, value, mid + 1, end));
	}
}

int query(int index, int left, int right, int start, int end) {
	if (left > end || right < start)
		return INF;
	if (left <= start && end <= right)
		return tree[index];
	int mid = (start + end) / 2;
	return min(query(index * 2, left, right, start, mid),
		query(index * 2 + 1, left, right, mid + 1, end));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	score.resize(n+1);
	for (int i = 1; i <= n; ++i)
		score[i].resize(3);
	int t;
	for (int i = 0; i < 3; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> t;
			score[t][i] = j; // 해당 학생의 등수 적어줌
		}
	}
	sort(score.begin(), score.end());
	fill(&tree[0], &tree[n * 4], INF);

	int res = 0;
	for (int i = 1; i <= n; ++i) {
		// 첫번째 시험 순서대로 정렬했으니 순서대로 비교(뒤에 있으면 늦게 업데이트되므로 두번째, 세번째만 비교해주면됨)
		// 쿼리로 두번째 시험의 1~score[i][1]등의 최소 세번째 시험 등수를 받아옴
		if (query(1, 1, score[i][1], 1, n) > score[i][2])
			++res;
		// 두번째 시험 등수에 세번째 시험 등수를 업데이트해줌(1~score[i][1] 쿼리 던질꺼기 때문에)
		update(1, score[i][1], score[i][2], 1, n);
	}
	cout << res << endl;
	return 0;
}

댓글남기기

참고