세그먼트 트리 중간값 의식의 흐름 BOJ 9426

세그먼트 트리로 중간값을 어떻게 구하지?

세그먼트 트리 두 개를 쓰는 식으로는 중간값 구하기는 어림도 없다.

 

(윗방법)

머리를 싸맨다.

일단 input들을 정렬하는 것을 시작으로 한다.

이렇게 정렬된 모든 숫자 전체를 세그먼트 트리의 리프 노드로 두고,

window에서 보고 있는 리프만 1, 그렇지 않으면 0을 리프에 준다.

그리고 위로 타고 올라갈수록 sum.

이 상태에서 중간값을 어떻게 찾지 고민하다가 답지를 폈다.

 

(아랫방법)

알고보니 가능한 숫자 전체 범위를 세그먼트 트리 리프로 놓으면 쉽게(?) 풀린다.

 

 

지금 보니 두 개념이 상당히 비슷하다.

언젠간 숫자 범위를 int 전체 범위로 줘서 아래 방법으로는 못푸는 문제를 내야지.

 

그런데 애초에 윗 방법으로 하면 중간값을 찾는 방법이 애매해진다.- 인줄 알았는데 그냥 잘만 된다.

(사실 정말로 다를게 하나도 없다)

그냥 잘만 되는 코드 : http://boj.kr/818db6fde652445395cc5da3f8d06691

공유 소스 보기

결국 중간값을 이진 탐색하듯 찾아낸다는걸 떠올려야 한다.

노드 수의 합계는 root와 가까운 쪽에 있기 때문에 꼭 중간값 index를 root 쪽에서, 총합계를 이용해 찾아야 한다고 생각했었는데, 그게 아니었다. 위에서부터 뭉텅이씩. 조금씩 조금씩 세가면서 아랫단으로 내려간다.