sgc109   2달 전

현재 세그트리를 공부하기위해 세그트리로  해결 가능한 여러 문제들을 세그트리로만 풀려고 하는 중입니다.


우선 제가 이 문제를 어떻게 풀어봤냐면


각 시험에서 순위별로 학생들의 번호가 주어진것을 바탕으로

1등은 10점, 2등은 9점, ... , 10등은 1점 이라는 점수를 부여한다는 전제하에(순위가높다 = 점수가 높다 이므로)

각각의 학생을 객체로하고 객체에 세 시험의 점수를 배열로 가지도록 구성한뒤

n명의 학생들의 정보를 담고있는 객체 배열을 첫번째 시험 점수를 내림차순으로 정렬하였습니다.

그리고 반복문을 돌리며 정렬된 배열에서의 0번째학생부터 n-1번째 학생까지 보면서 굉장한학생이 아닌지 여부를 확인한후 빈 세그트리에서 시작하여 update 시켜주는데

V[두번째시험점수] = 세번째시험점수  일때 V를 바탕으로 Range Maximum Tree 를 구성하는것입니다.

query(i번째 학생의 2번째 시험점수+1, n) 를 한 값이 i번째 학생의 3번째 시험점수보다 높다면 앞서 세그트리에 update 한 학생들중

두번째시험과 세번째시험 점수가 높은 학생이 최소한 한명은 있는건데, 왜냐하면 맨처음에 1번째 시험점수를 기준으로 내림차순 정렬을 하였으므로 앞서서 등록되었다는것은 첫번째 시험 점수도 높다는 뜻이므로 누군가 대단한학생이 한명은 존재하는것이라는 것을 알게되므로 특정 변수에 누적시킵니다(굉장하지않은 학생의 수를 구한뒤 마지막에 전체 학생수에서 빼서 답을 냅니다.)

그리고 update(i번째 학생의 2번째 시험점수,i번째 학생의 3번째 시험점수) 를 해줍니다.

첫번째 시험 점수를 기준으로 내림차순 정렬하였으므로 앞서 update 되어있는 학생들은 무조건 현재 학생보다 첫번째 시험점수가 높으며

현재 보다 나중에 나오는 학생은 현재 학생보다 대단한 학생일 수가 없습니다.


여기까지가 제가 푼 방법입니다. 하지만 예제와 제가 만든 테스트 케이스들에서는 맞는 결과가 나오는것같은데

5% 에서 틀렸습니다. 가 떠서 어디서 잘못된건지 계속 찾다가 못찾겠어서 올립니다.

댓글을 작성하려면 로그인해야 합니다.