[백준] 2336 굉장한 학생

문제가 처음에 이해하기 어려웠다

3과목을 시험보는데 A가 B보다 모든과목을 잘보면 '대단한 학생'

C라는 학생보다 '대단한 학생'이 한명도 없다면 '굉장한 학생' 이다

처음에 세그먼트 트리를 2개 만들어서 비교하려했는데 실패했다 ㅎㅎ

3과목이라 조건이 3가지이기 때문에 아이디어를 잘 떠올려야 한다

문제를 푸는 방법은

1. 첫번째 등수 기준으로 정렬을 한다

2. 세그먼트 트리를 만든다. 이 때 트리는 최소값 트리다

3. 트리의 i번째에는 두번째 과목을 i등한 사람의 3번째 과목 등수를 넣는다

4. 0~n-1까지 for문을 돌며 두번째 과목 등수까지의 값이 3번째 등수 값보다 크다면 이학생은 굉장한 학생이다!

이렇게 3가지 조건을 다 만족시켜주게 트리를 만들면 되는데.... 어렵다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define INF 987654321
struct Node {
    int A, B, C;
    bool operator < (const Node &other) const {
        return A < other.A;
    }
};
int query(vector<int> &tree, int node, int start, int end, int i, int j) {
    if (j<start || i>end) return INF;
    if (i <= start && end <= j) return tree[node];
    return min(query(tree, node * 2, start, (start + end) / 2, i, j), query(tree, node * 2 + 1, (start + end) / 2 + 1, end, i, j));
}
void update(vector<int>&tree, int node, int start, int end, int index,int val) {
    if (index<start || index>end) return;
    if (start == end) {
        tree[node] = val; return;
    }
    update(tree, node * 2, start, (start + end) / 2, index,val);
    update(tree, node * 2 + 1, (start + end)/2 + 1, end, index,val);
    tree[node] = min(tree[node * 2] , tree[node * 2 + 1]);
}
 
int main() {
    int n;
    scanf(" %d", &n);
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h + 1));
    vector<Node> a(n);
    vector<int> tree(tree_size);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            int x; scanf(" %d", &x);
            if (i == 0) a[x-1].A = j;
            else if (i == 1) a[x-1].B = j;
            else a[x-1].C = j;
        }
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) update(tree, 1, 0, n - 1, i, INF);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int Bpos = a[i].B;
        int Cpos = a[i].C;
        if (query(tree, 1, 0, n - 1, 0, Bpos) > Cpos) ans += 1;
        update(tree, 1, 0, n - 1, Bpos, Cpos);
    }
    printf("%d\n", ans);
}