https://www.acmicpc.net/problem/22899
요약
- N개의 문제 중 K개를 출제하는데, 총 출제 시간을 적게 해야함
- 문제마다 출제가능한 사람이 1명씩 주어짐
- 문제마다 출제에 가능한 시간이 주어짐
- 1사람당 출제 가능한 문제 횟수의 제한을 1 -> N으로 변경할 때 각각의 값을 구하는 문제
접근법
- 어려운 문제였고, 티어가 골드인 것을 보고 그나마 도전해보게 됨
- 일단 인당 출제제한이 없었다면...(출제제한이 N이라면) 자유롭게 전체 문제에서 소요시간이 작은 K개를 출제 할 것임
- 출제제한을 N - 1, N - 2, ... 로 줄이다 보면 언젠가 출제제한에 걸리는 사람이 나타날 것임
- 그 사람이 출제한 문제중 가장 높은 시간을 일단 뺌 => 사람별 우선순위큐 사용
- 그리고 남은 문제에서 소요시간이 작은 것을 출제하는데
- 이미 출제할 사람 횟수가 꽉 찼다 -> 앞으로 그 문제는 출제 못할 것임
- 차지 않았다? -> 일단 출제
- 구현을 위해 복잡한 요소가 많았음
- 사람당 출제 횟수 카운팅을 유지함
- 사람당 출제한 문제를 우선순위 큐로 관리함
- 허들(출제제한)에 걸리는 사람을 찾기 위해 [카운팅]에 사람을 넣어놓음
- 카운팅이 변하는 처리를 안해주고 변하는 데로 다 집어넣음
- 안될 것 같고 중복이 생기긴 하는데 잘 생각해보면 문제 수만큼 변경이 일어나서 적절한 것 같음
다른 사람 풀이
- 왜 내 생각보다 티어가 낮을까 생각하다가 어떤 분 풀이를 봄
- 풀이는 심플함, 보석 도둑 컨셉같은 것 ==> 할 수 있는 할당량을 늘려가면서 풀을 만들고 섞고, 제외하고....
- 요약하면, 사람당 문제를 모으는데 시간이 적게 소요되는 순으로 정렬해놓음
- 일단 인당 "1"만큼 해당하는 것들을 다 모음
- 다 모았는데 K가 안된다? => 안되는 것임
- 다 모았은데 K가 넘는다? => 큰것부터 배제시킴. 왜냐하면 배제시킨 것들은 앞으로도 배제 될 것이기 때문임
- 그 다음은 "2"만큼 해당하는 것 까지 다 모아서 섞음....반복
- 이런 방식이 되는 이유가, 문제당 한 사람만 할당이 되기때문임
newbieski