https://www.acmicpc.net/problem/17942
문제요약
- 공부할 알고리즘들이 주어지고, 각각에 필요한 공부양이 주어짐 (10만개, 10^8)
- 연관성이 주어짐 : A를 공부하면 B의 공부양이 D만큼 줄어듬. 줄어드는 양은 합산 가능
- 공부를 했다고 공부양이 없어지지는 않음 => 100의 능력치를 가지고 계속 공부를 한다고 보면 됨
- M개의 알고리즘을 공부하기 위해 최소로 필요한 공부양(능력치)
접근법 - 실패
- 위상정렬 + 파라메트릭 서치로 하려고 했음
- 위상 정렬 순서로 훑으면서 특정 값으로 되는지 안되는지로 판단
- cycle이 생기는 것을 간과했음
접근법 - 성공
- 가장 작은 알고리즘 공부양이 있을 것임
- 작은 공부양이 혹시라도 더 줄어들 수 있지만, 더 줄어들기 위해서는 더 큰 공부양으로 진행을 해야할 것임
- 가장 작은 알고리즘 공부양은 어짜피 필요한 최소 공부양임
- 가장 작은 알고리즘 공부양을 진행하면 관련된 것들이 업데이트 될 것임
- 그리고 나서 가장 작은 공부양이 있을 것이고
- 이렇게 반복하다보면 언젠가 M개를 넘게 공부할 것임. 그리고 마지막으로 사용한 공부양(=능력치)이 있을 것임
- 그리디(작은 공부양부터) + 우선순위큐(가장 작은 공부양)
- 이미 공부한 알고리즘은 방문체크
newbieski