[platinum3][풀이, 분류 미확인] boj5461 고용

 

 

재미있는 우선순위 큐 문제였다.

사람마다 최저 임금 Si와 기술 비용 Qi 가 있을 때 , Qi * K  를 했을 때 최저임금을 넘어야 한다.

그런데, 모든 사람에게는 K가 같아야 한다. 

각 사람마다  Ki = Si / Qi 라고 하면,  그 사람의 비용 >= Qi * Ki = Si  가 되어야 한다. 

 각 사람마다 Ki가 다를 수 있는데, 이 문제에선 K가 모든 사람에게 동일하게 적용되어야 한다.

Qi * K  = i번째 사람의 비용 이기 때문이다.    즉 모든 사람에겐 동일한 K값이 주어지므로, K는 뽑은 사람중 K값이 가장 큰 사람의 값이어야 한다.

 

위와 같은 예시가 있을 K는 3.5가 될 것이다. K가 3.5보다 작으면 사람3의 최소비용이 충족되지 않기 때문이다.

 

즉 사람을 뽑았을 때 뽑은 사람들의 Ki중 최댓값을 고려해야 할 것이다.

 

총 비용은 (Qi 총합 ) * (Ki 최댓값) 이 될 것이다.

 

여기서 직관적으로 들 수 있는  생각은 모든 사람들의 Ki값들을 오름차순으로 정렬한 후, 반복문을 돌며 i번째 사람들중 Qi값을 고려하면 될 것이라는 것이다.

i 번째에서 Ki의 값은       K1 ~ Ki-1 값보다 크기 때문에, 무조건 Ki가 최댓값이고, 그렇다면, 이제 총 비용은 (Qi총합) *(Ki최댓값)인데 Ki 최댓값은 정해졌으므로, Qi만 고려하면 된다는 생각이다. 그럼 이제 사람수를 최대로 하면서, 사람수가 같다면 Qi의 총합을 최소로 해야 한다. 

 이것은 우선순위 큐로 해결이 가능하다.

     i번째에서 Q의 값을 내림차순으로 설정한 우선순위큐 (qpq 라 한다). 가 있으면, 일단 i번째의 Qi값을 qpq에 넣는다. 그럼 이대 넣었을 때 Qi의 총합 * (K의 최댓값) > W(가지고 있는 돈의 최댓값) 이라면  pqp에서 한개를 poll한다. 그럼 제일 큰 Q값이빠지므로, 무조건 W보다 작거나 같아진다. Qi의 총합 * (K의 최댓값) <= W  라면 pqp를 poll하지 않는다. 

그럼 이제 qpq의 사이즈가 i번째에서 가능한 최대로 고를 수 있는 사람의 수가 된다.  1~K번째까지의 사람들 중 Q가 가장 작은 순서대로, Q의 총합이  (W) / Ki 까지일때의 사람들만 pqp에 남았기 때문이다.

이렇게 하면 i 번째에서  사람의 최댓값을 얻을 수 있고, 만약 최댓값이 기존의 최댓값과 같다면 기존의 pqp의 총합 * 기존의 K최댓값 과 비교해 비용이 낮은 것을 답으로 하면 된다.

 

비용이 가장 낮을 때 사람들을 출력하기 위해  첫번 째 pq에선 최대 사람수,  그대의 최소 비용을 구한후,  같은 원리의 pq를 다시한번 반복하다가 이미 구한 최대사람수, 최소 비용이 나오면 정답의 pqp에 있는 사람들을 출력하도록 하였다. 또한 k는 정수가 아닐 수도 있으므로, k끼리 비교시 (S1 / Q1 > S2 / Q2)시 (S1 * Q2 > S2 * Q1)식으로 분모가 없도록 비교하였다.(이때 오버플로우  조심하자)