[BOJ 13334] 철로 "컷"

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

 

http://boj.kr/d7291475a4294aa58c892481968bf9e3  

문제를 보자 말자 세그나 mergesort tree 풀이만 생각나서 고생했다.

골드2인데, 그게 정해일리도 없을 뿐더러, 구현이 빠른 풀이를 생각해보고 싶었다.

 

문제를 보면 2가지 접근이 기본적으로 생각난다. 스위핑 혹은 파라메트릭 서치.

이 문제의 경우 파라메트릭이 오히려 더 어렵다. 바로 스위핑으로 접근해도 된다.

위치를 받아서 선분 형태로 만들어주고 끝점 기준으로 정렬한 뒤 시작 점들만 관리해주면 된다.

현재 보고 있는 끝점을 b라 했을 때  지금까지 추가해준 시작점들 중에서 b-d 이상인 개수만 구해주면 된다.

시작점을 a라 하면 a도 정렬되게 관리해주면 좋다. multiset에 집어넣자. 그런데 multiset은 기본적으로 특정 수 이상의 수 개수를 셀 수가 없다. (가능한 자료 구조 -> pbds Ordered set). 따라서 처음부터 multiset을 b-d 이상의 수만 들어가게 관리하자. 일단 multiset에 추가하고 앞에서 b-d 미만인 수들을 지워나가면 된다. 모든 수는 1번 추가, 최대 1번 제거 되므로 amortized O(nlogn)에 모든 작업이 완료된다.

 

웃긴풀이: 시작점, 끝점 아예 따로 관리한다. 처음에 d 초과인 선분들을 다 컷하고 알아서 잘 스위핑해줌. 되게 신기함.

 

정석풀이: 사실 a를 정렬된 상태로 유지할 필요 없다. 가장 작은 원소만 없앨 수 있으면 된다. => 우선순위 큐