coordinate_compression 썸네일형 리스트형 BOJ 29202 - 책가방 (D5) 2023 KSA Automata G번이다. 아레나 당시에 27점까지 긁었는데, 27점 풀이로 44점까지 긁을 수 있었다는 걸 대회 때 알았으면 더 좋았을 것 같다. 사용 알고리즘 Segment Tree + 좌표 압축 && 그리디 (우선순위 큐) 풀이 일단 섭태3을 풀어보자. 부피의 최댓값만 고려하면 되므로 부피 기준으로 오름차순으로 정렬하고 정렬된 배열에서 x번 책을 고르면, 1~x-1 사이 책은 모두 부피가 \( V_{x} \) 이하이다. 따라서 이 중에서 무게가 작은 k-1개를 골라주는게 이득이다. 이는 우선순위 큐(max heap)의 크기를 k-1으로 유지하고, 하나의 변수를 관리하는 것으로 해결할 수 있다. for(int i = 0 ; i < n ; i++)v[i].i=i+1; sort(all(v.. 더보기 이전 1 다음
