221208 문제 풀이 기록

P4 | 5461 - 고용

풀이 시간: 굉장히 오랜 시간

시도 횟수: 굉장히 많은 횟수

체감 난이도: P3

풀이 쓸 의향: 中

풀이

Q 1당 드는 비용을 K라고 하면, 어떤 고용인 조합 X에 대해 K=max(S_i/Q_i) for i <= X가 된다. K를 오름차순으로 정렬하여 순서대로 생각해보면, K * sum(Q) <= w여야 하고, 이때 최적의 방법은 지금까지 나온 Q 중 가장 작은 고용인들만 순서대로 최대한으로 고용하면 된다. K가 커지면 지금 사용한 Q값보다 더 큰 Q를 절대로 더하지 않으므로 (본인 차례 제외), pq를 사용하여 구현할 수 있다.

여담: "만약 고용할 수 있는 노동자의 수가 같다면, 노동자들에게 최소 비용을 지급하는 고용 방안을 원하며"... 이걸 못봐서 다 풀어놓고 대가리박고 있었다.

 

 

 

P3 | 11873 - 최대 직사각형

풀이 시간: 30분 + a (예전에 풀다 때려쳤던 경험 있음)

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

히스토그램(1725번) N번씩 해주기

여담: 예전에 이 문제 봤을때는 2차원 구간합 구현해놓고 "이걸 어케 풀어;"하면서 던졌었는데, 다시 보니까 바로 "그 문제" 삘이 나서 바로 풀었다.