[백준] 2336_굉장한 학생 (C++)

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

2336번: 굉장한 학생

---

정렬과 세그먼트트리를 이용하여 해결 할 수 있다.

 

입력 후, 첫번 째 등수에 대해서 x축 정렬한 결과.

1번 학생 : 0등 1등 7등

2번 학생 : 1등 4등 4등

3번 학생 : 2등 2등 0등

4번 학생 : 3등 7등 1등

5번 학생 : 4등 9등 3등

6번 학생 : 5등 6등 2등

7번 학생 : 6등 0등 6등

8번 학생 : 7등 5등 8등

9번 학생 : 8등 8등 9등

10번 학생 : 9등 3등 5등

 

 

로 정렬한뒤에 1번학생 ~ 10번 학생을 처리 하게 되는데,

1번학생은 반드시 굉장한 학생이 될 것이다.

2번학생은 오직 1번학생보다 하나만이라도 높다면 굉장한 학생이 될 것이다.

3번학생은 1,2번학생보다 등수가 모두 높다면 높다면 굉장한 학생이 될 것이다.

...

N번 학생은 N-1학생보다 등수가 다 높다면 굉장한 학생이 될 것이다.

< 1번 학생 >

1번째 리프노드 7로 update

< 2번 학생 >

0~3번 중 최솟값이 현재 7이므로 굉장한 학생이다

4번쨰 리프노드 4로 update

< 3번 학생 >

0~1번중 최솟값이 현재 7이므로 굉장한 학생이다

2번째 리프노드 0으로 update( 이학생 때문에 뒤의 학생들은 대부분 굉장한 학생이 아니게 된다 )

< 4번 학생 >

0~5번중 최솟값이 0이므로 이학생은 굉장한 학생이 아니다.

7번째 리프노드를 1로 update

.... 반복 ....

---

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 500000

class Info {
public :
     int x, y, z;
     Info() {}
     Info(int x, int y, int z) {
          this->x = x;
          this->y = y;
          this->z = z;
     }
     bool operator < (const Info & b) const {
          return this->x < b.x;
     }
};

Info arr[MAX_N];
int tree[MAX_N * 4];

void init_tree(int now, int start, int end) {
     if (start > end) return;
     if (start == end) {
          tree[now] = 1e9;
          return;
     }
     int mid = (start + end) / 2;
     tree[now] = 1e9;
     init_tree(now * 2, start, mid);
     init_tree(now * 2 + 1, mid + 1, end);
}

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

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

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].x = i;
     }
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].y = i;
     }
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].z = i;
     }
     sort(arr, arr + N);
     init_tree(1,0,N-1);
     int ans = 0;
     for (int i = 0; i < N; i++) {
          int y = arr[i].y;
          int z = arr[i].z;
          if (getMin(1, 0, y, 0, N - 1) > z) ans++;
          update_tree(1, y, 0, N - 1, z);
     }
     cout << ans << "\n";

}

---

나한텐 너무 어려운 문제였지만, x,y,z를 묶어서 sort뒤의

출력물을 보고나서 쉽게 접근 할 수 있었다.