https://www.acmicpc.net/problem/3430
문제 요약
- 호수(n), 날짜(m), 각각 10^6
- 비가 오기도 하고(한 호수에만 옴), 안오기도 함
- 호수가 차있을때 비가 오면 재앙
- 비가 안올때 용은 호수의 물을 비울 수 있음
- 재앙을 막을 수 있는지, 막는다면 어떻게 막는지
- 초기에 호수에 물은 차있음
접근법
- 일단 직관적으로 비가 오는 호수에 물을 가장 빠른 시점에 비우면 될 것 같음 ==> 최소한 손해는 안보니까
- 스택처럼 해야하나 했는데 물을 비운 후에 비가 내리고 나서의 처리가 까다로움
- 어떤 호수에 비가 오면 그 전날 중에서 가장 빠른 날짜를 찾으면 되겠는데, 그냥 전날은 아니고 마지막으로 비가 온 날 이후 중에서 가장 빠른 날짜를 찾고 싶음
- 이 부분에서 구간트리를 생각했음
- 비가안온날중 최소값(마지막 비가 온날, 현재) 을 구해서 뭔가가나오면 성공이고 안나오면 실패. 안나오게 처리는 MAX 값을 넣어놓음
- 성공시에는 그 곳에 MAX를 넣어서 앞으로 안나오게 처리하고, 정답으로 출력할 처리도 함
다른 접근법
- 우선순위큐 사용
- 구간트리 아이디어를 다시 생각해보면 됨
- 비가오는 가장 가까운 날짜를 우선순위 큐에서 관리
- 물을 비울 수 있는 날에는 우선순위큐의 가장 앞에 있는 것을 선택
- 비가 오는 날에는 호수가 비어있으면 물을 채우고, 이후에 나타날 것 중 가장 앞에 있는 것을 선택. 그리고 이후에 나타날 것 중 가장 앞에있는 것을 선택하기 위해 전처리를 하든 이분탐색을 하든 하면 됨
- 호수가 차있으면 실패 처리
후기
- 어려운 문제였음
newbieski