BOJ 2912 백설공주와 난쟁이 Java 세그먼트 트리 이진탐색

백준 2912번 백설공주와 난쟁이https://www.acmicpc.net/problem/2912

세그먼트 트리, 이진탐색 알고리즘 문제

세그먼트 트리 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8%ED%8A%B8%EB%A6%AC

이진탐색 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89

 

너무 어려워서 잡히는 줄 알았다....ㅠㅠㅠ

인덱스를 이용해 자식노드에 접근할 일이 없으므로 세그먼트로 풀기에 좋은 문제

 

세그먼트 트리는 루트부터 값이 들어가게 되므로 이런 형태로 그려진다.

(색상명,난쟁이수)쌍으로 구성

 

그룹별 난쟁이 인덱스값을 받아서 이진탐색의 Upper Bound와 Lower Bound를 이용해 (가장 오른쪽의 난쟁이 - 가장 왼쪽의 난쟁이)를 이용해 난쟁이수를 구한다.