[BOJ 2336] 굉장한 학생

 

[문제] : https://www.acmicpc.net/problem/2336

2336번: 굉장한 학생

 

[난이도]

 

- Platinum 2 (2020.08.05 solved.ac 기준)

 

 

 

[개념] 

 

- 세그먼트 트리 (Segment Tree)

 

 

 

[풀이]

 

우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 

 

문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고 한다. 이때 굉장한 학생의 수를 구하는 것이다. 

 

만약 문제 조건이 세 번의 시험이 아니라 "두 번의 시험"이라면 다음과 같이 풀이를 할 수 있을 것이다.

 

1. 시험1을 기준으로 등수를 오름차순으로 정렬한다. 그렇다면 앞에 있는 학생은 반드시 뒤에 있는 학생들보다 시험1은 등수가 더 높다.

2. 정렬된 학생들을 처음부터 끝까지 시험2 등수의 최솟값을 갱신해 나가면서 탐색한다.

3 - 1. 현재 학생의 시험2 등수가 이전까지의 시험2 등수의 최솟값보다 작은 경우, 앞의 모든 학생들보다 시험2의 등수가 높고, 뒤의 모든 학생들보다 시험 1 등수가 높으므로 문제 조건을 만족한다. 

3 - 2. 현재 학생의 시험2 등수가 이전까지의 시험2 등수의 최솟값보다 큰 경우, 앞의 적어도 한 학생이 현재 학생보다 시험2의 등수가 높으므로 문제 조건을 만족하지 않는다. 

 

하지만 이 문제는 세 번의 시험이기 때문에 위와 같은 방식을 적용시키기가 까다롭다. 나머지 두 시험의 최솟값보다 더 작지 않아도 문제 조건을 만족하는 경우가 생기기 때문이다. 

따라서 이 문제를 풀기 위해서 세그먼트 트리(Segment Tree)를 이용한다. 

 

(세 시험의 점수를 각각 A, B, C라고 순서대로 표기하겠다.) 

 

첫 번째로, 첫 번째 시험을 기준으로 정렬하는 것은 동일하다. 사실 어느 시험으로 정렬하는가는 크게 문제가 되지 않는다. 이 과정을 통해서 비교해야 하는 시험 하나를 줄일 수 있게 된다. 

 

그다음, Tree의 모든 원소를 MAX로 초기화시켜 놓은 후, 현재 학생의 B 자리에 C를 저장하는 것이다. (update)

현재 학생이 '굉장한' 학생인지 체크하기 위해서는, Tree의 [1 ~ B-1] 구간의 최솟값을 먼저 구한다. 

이때, 최솟값이 MAX가 아닌 경우, 이전까지 학생 중에서 시험2의 성적이 더 좋은 학생이 존재한다는 뜻이다. 

그리고 그 최솟값이 만약 C보다 작은 경우에는 이전까지 학생 중에서 시험3의 성적이 더 좋은 학생이 존재한다는 뜻이므로 결국 세 시험의 성적이 모두 현재 학생보다 좋은 학생이 존재하게 된다. 

 

그러므로 "[1 ~ B-1] 구간의 최솟값 > C" 를 만족하면 현재 학생은 '굉장한' 학생이 된다. 

 

 

 

소스 코드)

 

 

#include<iostream>
#include<algorithm>
#include<vector>
 
#define MAX 2e9
 
using namespace std;
struct exam {
    int a, b, c;
    bool operator < (exam E) {
        return a < E.a;
    }
};
int tr[2000001];
int update(int x, int s, int e, int i, int val) {
    if (i < s || i > e) return tr[x];
    if (s == e) return tr[x] = val;
    else {
        return tr[x] = min(update(x * 2, s, (s + e) / 2, i, val), update(x * 2 + 1, (s + e) / 2 + 1, e, i, val));
    }
}
int mi(int x, int s, int e, int l, int r) {
    if (s > r || e < l) return MAX;
    else if (s >= l && e <= r) return tr[x];
    else return min(mi(x * 2, s, (s + e) / 2, l, r), mi(x * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int N; cin >> N;
    for (int i = 1; i <= 4 * N; i++) tr[i] = MAX;
    vector<exam> v(N + 1);
    for (int i = 1; i <= N; i++) {
        int a; cin >> a;
        v[a].a = i;
    }
    for (int i = 1; i <= N; i++) {
        int a; cin >> a;
        v[a].b = i;
    }
    for (int i = 1; i <= N; i++) {
        int a; cin >> a;
        v[a].c = i;
    }
    sort(v.begin()+1, v.end());
 
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (mi(1, 1, N, 1, v[i].b) > v[i].c) ans++;
        update(1, 1, N, v[i].b, v[i].c);
    }
    cout << ans;
}
 

 

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^