백준 2336

2336번: 굉장한 학생

 

  첫 번째 시험을 기준으로 오름차순으로 정렬한다. 그러면 어떤 학생을 기준으로 그 앞에 있는 학생은 모두 첫 번째 시험에서 그 학생보다 좋은 성적을 받은 학생이다. 여기서 두 번째, 세 번째 시험도 더 잘 친 사람이 있는지 체크하면 된다. 두 번째 시험을 나보다 잘 친 사람이 없다면 정답이 하나 증가하고 그렇지 않은 경우 두 번째 시험을 나보다 잘 친 사람들 중에서 나보다 세 번째 시험을 잘 친 사람이 있는지 확인하면 된다.

 

  세그먼트 트리의 리프 노드 i를 두 번째 시험 등수가 i인 학생의 3 번째 시험 등수로 정의하고 첫 번째 학생부터 검사해 나가면 된다. 현재 보고 있는 학생이 i라면 [1, i - 1] 범위를 확인하면 된다. 현재 나보다 두 번째 시험을 잘 친 사람이 없다면 모두 초깃값 INF를 반환하고, 있다면 어떤 최솟값 m을 반환한다. 그 값을 지금 보고 있는 학생의 세 번째 값과 비교하자.

 

  삽질 기록 : i  번째 세로줄의 의미가 i 번째 학생이 첫 번째 시험 등수, 두 번째 시험 등수, 세 번째 시험 등수인 줄 알고 삽질했다. 실제 의미는 각 시험에서 성적이 높은 순으로 "학생 번호"를 나열한 것. 이 덕분에 삽질 1시간 했다.

 

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%202336.cpp