굉장한 학생( BOJ 2336 )

문제

2336. 굉장한 학생 : https://www.acmicpc.net/problem/2336

2336번: 굉장한 학생

 

문제 파악하기

• 나보다 모든 시험을 잘 본 학생이 없는 경우, 굉장한 학생이 됩니다.
• N이 500,000이기 때문에 단순 for문으로는 힘듭니다.
• 이 경우, 세그먼트 트리를 차근차근 채워넣으면 문제를 해결할 수 있습니다.

 

문제 해결하기

• 우선 첫번째 시험 결과 순서대로 세그먼트 트리에 값을 저장합니다.
• 세그먼트 트리에 저장하는 위치는 두번째 시험을 기준으로 합니다. 두번째 시험의 등수 위치에 현재 학생의 값을 저장합니다.
• 세그먼트 트리에 저장하는 값은 세번째 시험 등수입니다.
• 이렇게 세그먼트 트리를 구성하면 현재 노드보다 왼쪽에 있는 학생들은 나보다 첫번째, 두번째 시험을 잘 본 학생이라는 의미입니다.
  여기서 세번째 시험 결과까지 확인하면 현재 노드가 굉장한 학생인지 여부를 알 수 있습니다.
• 세그먼트 트리는 등수를 저장하기 때문에 최소 세그먼트 트리로 구현하면 됩니다.

 

후기

세그먼트 트리를 이렇게 사용할 수도 있다는 걸 보여준 문제라고 생각합니다. 세그먼트 트리의 활용 문제로 추천드립니다.