yukariko   1년 전

이 문제의 솔루션을 다음과 같이 생각해봤습니다.

0. 답의 최솟값 = 모든 원소들의 차이를 최소로 하면서 사탕을 전부 소모하는것

1. 힙을 생성해서 원소들을 전부 push

2. 매 반복마다 pop을 하여 그 다음 top 과의 차이 + 1 만큼 제거 한 후, 0보다 크면 push

3. 탈출조건 : 힙이 비거나, 사탕을 전부 소모 또는 pop한 원소가 1이면(힙의 원소가 1밖에 없음)

4. 힙에 남은 원소들을 각자 제곱해서 더함

5. 결과가 0이면 0, 0보다 크면 남은 사탕수만큼 빼고 출력(사탕이 남는 경우는 결과가 0이거나 힙이 1로만 채워진 경우기 때문에 빼도 무방)


그런데 시간초과가 뜨더군요 ㅠㅠ

시간복잡도가 O(nlogn) 일거 같은데 시간초과라 어떻게 해야할지 감이 안잡히네요

제 생각에 틀린점이나 더 쉬운 방법이 있다면 답변 부탁드려요

풀이도 Introsort를 사용하니까 nlogn이네요.

댓글을 작성하려면 로그인해야 합니다.