PG) 야근지수 -lv3

https://school.programmers.co.kr/learn/courses/30/lessons/12927

 

import heapq

def solution(n, works):
    if n >= sum(works):
        return 0
    
    works = [-i for i in works]
    
    heapq.heapify(works)
    
    for _ in range(n):
        mx = heapq.heappop(works)
        mx += 1
        
        heapq.heappush(works,mx)
        
    
    return sum([i ** 2 for i in works])

 

제곱근의 합 중 가장 작은 수를 구하는 문제이다.

이렇게 말로 들으면 어떻게 풀어야할지 감이 잡히지만 사실 이 문제는 1시간을 고민했고 답을 도출하지 못했다.

 

제곱근의 합에서 가장 큰 수를 구하기 위해선 가장 큰 값을 줄여주어야한다.

 

하지만 배열을 정렬하는 과정에서는 시간 초과가 나오기 때문에 heap정렬을 이용해 정렬을 수행해야한다.