세그먼트 트리가 뭔지는 알고 있었는데, 개념 정도만 익히고 있었지 실전에서 이게 쓰일까 싶은 생각에 머리 속 깊은 공간에 간직만 하고 있었음.


이 문제를 만나기 전까진.


https://www.acmicpc.net/problem/1517

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


처음에는 이진 탐색으로 손십게 풀릴줄 알고 배열에다 인덱스 담아두고 이진탐색으로 가장 가까우면서 큰 값 인덱스 출력해서 그만큼 보정해주는 코드를 짰음.


(핵심 코드)





근데 계속 3프로때에서 시간초과가 뜨길래 ㅅㅂ 뭐가 문제지 하고 머리싸매고 있다가, 머리를 탁 치고 드디어 "세그먼트 트리" 가 나설 차례인가 라는 생각이 듬



(바퀸 코드) 





사실 솔직하게 고백하면 세그먼트 트리만 구현한 부분은 어디서 긁어옴....ㅋㅋㅋㅋ


그래서 내 손으로 직접 구현까지 해보면서 오늘의 ps일자를 마무리 해볼까 함



후....부랄이 떨리네 이게 세그먼트 트리의 맛이구나....