https://www.acmicpc.net/problem/20666
문제요약
- 몬스터는 N개가 주어지지만 M개만 잡으면 됨
- 몬스터별 아이템을 얻을 수 있음
- 몬스터별 난이도가 있음
- a아이템 없이 b몬스터를 잡을경우 t만큼 어려워진다는 조곤이 30만개 주어짐
- 최고 난이도를 최대한 줄이기
접근법 - 파라메트릭 서치
- 접근법이 틀린건 아니었지만 구현이 틀렸음
- 최대 난이도를 K로 정하고 되는지 안되는지를 판단하면서 값을 조정하는 접근법
- 난이도가 작은것들부터 처리하면서, 그로인해 난이도가 변경되는 것들을 처리하는 방식 : 우선순위 큐 + 처리 완료 배열 사용
- 난이도가 K이하인 것들은 우선순위큐에 넣음
- 여기서 구현 오류가 있었음
- 몬스터를 잡고 -> 아이템을 얻고 -> 그로인해 난이도가 변경되는 몬스터가 생기고 -> K 이하이면 우선순위 큐에 넣었음
- 이후 다른 몬스터를 잡고 -> 이미 우선순위큐에 들어간 몬스터의 난이도가 변경되는 경우 -> 무시했음
- 그런데 무시하면 안됨 왜냐하면, 이미 들어갔더라도 난이도 변경으로 인해 더 빨리 우선순위큐에서 나오게 될 수도 있기 때문임
- 그로 인해 K 이하 처리가 달라질 수도 있음
접근법 - 그리디
- 굳이 K값을 조정할 필요가 없음
- 난이도가 낮은것부터 처리하면서 M개를 처리했는지만 보면 됨
- 우선순위큐에서 꺼낸 값이 항상 증가하지는 않음에 주의
- 난이도가 변경될때마다 우선순위큐에 새로 넣기때문에, 이미 처리된 것들을 다시 처리하지 않도록 구현해야함
newbieski