https://www.acmicpc.net/problem/21279
접근법
- 시작점이 고정이고(0,0) x, y가 증가하는 방향으로 진행됨
- x 점 기준으로 세로 선을 놓는다고 할때, y 가 증가하는 방향으로 갈 수록 담아야하는 보석의 수도 증가할 것임
- C를 넘지 않는 y 좌표가 어디인지 판단하는 방법
- 이분탐색 : 값을 업데이트 할때마다 전체 배열을 갱신해야함
- 구간트리 : k 번째 수 찾는 테크닉
- 값이 있는 x점을 탐색할때마다
- 구간트리 업데이트
- C를 넘지 않는 y 좌표 판단
- y 좌표까지의 보석의 가치 합 계산
주의점
- k번째 수를 찾는 테크닉에서 C를 넘지 않는 y 좌표 판단에 주의
- 0번점에 C개 이상의 보석이 몰려있는 경우 주의
추가 고민
- 우선순위 큐를 사용한다면?
newbieski