문제
배상 비용은 선박 완성까지 남은 작업량을 제곱하여 모두 더한 값
남은 작업 시간 N을 이용하여 배상 비용을 최소화
작업 가능한 남은 시간 : N
각 일에 대한 작업량 : works
N은 1,000,000이하의 자연수
works의 크기는 1,000 이하의 자연수
각 일에 대한 작업량 : 1,000 이하의 자연수
입출력 예시
| N | works | return |
|---|---|---|
| 4 | [4, 3, 3] | 12 |
접근
제곱의 합을 최소화하기 위해서는 원소의 최대값을 낮춰야 한다.
따라서 현재 원소들의 최대값을 -1 하는 것을 N 번 반복한 결과가 최소일 것이다.
최대 힙을 이용하면 최대값을 찾는 부분을 빠른 시간안에 해결할 수 있다.
파이썬은 최소 힙밖에 제공을 안하므로, 최소힙에 원소를 음수로 만들어서 넣으면 그게 최대 힙이다.
주의할 점은 모든 원소가 0이 되는 경우이다.
이때는 break를 걸어 반복을 빠져나와야 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
def solution(no, works):
heap = []
result = 0
for work in works:
heapq.heappush(heap, work * -1)
for i in range(no):
item = heapq.heappop(heap)
if item == 0:
break
item += 1
heapq.heappush(heap, item)
for item in heap:
result += item * item
return result