백준 온라인 저지, 그리디 / 2878번: 캔디캔디 (파이썬 / 백준 골드문제)

문제

오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다.

택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다.

놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다.

예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다.

택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 최소화해 그 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M(1 ≤ M ≤ 2×10⁹)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×10⁹보다 작으며, 친구들이 받고 싶어하는 사탕의 개수의 합은 항상 M을 넘는다.

출력

첫째 줄에 택희 친구들의 분노의 합의 최솟값을 2⁶⁴로 나눈 나머지를 출력한다.

제한

예제 입력 1

5 3
1
3
2

예제 출력 1

1

예제 입력 2

10 4
4
5
2
3

예제 출력 2

4

힌트

W3sicHJvYmxlbV9pZCI6IjI4NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlOTRcdWI1MTRcdWNlOTRcdWI1MTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyNFx1YjI5OCBcdWMwYWNcdWQwZDUgTVx1YWMxY1x1Yjk3YyBcdWFjMDBcdWI0ZGQgXHViMmY0XHVjNzQwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWQwZGRcdWJjMzBcdWI4NWMgXHVkMGRkXHVkNzZjXHViMTI0IFx1YzlkMVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWIyZTQuIFx1ZDBkZFx1ZDc2Y1x1YjI5NCBcdWM3NzQgXHVjMGFjXHVkMGQ1XHVjNzQ0IE5cdWJhODVcdWM3NTggXHVjZTVjXHVhZDZjXHViNGU0XHVjNWQwXHVhYzhjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZGRcdWQ3NmNcdWM3NTggXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWMwYWNcdWQwZDVcdWM3NDQgXHViYTg3IFx1YWMxYyBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNzQwXHVjOWMwIFx1YmNmNFx1YjBjOFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YmMxYlx1YWNlMCBcdWMyZjZcdWM3NDAgXHVhYzFjXHVjMjE4XHViOWNjXHVkMDdjIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWJjMWJcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0XHViYTc0LCBcdWFkZjggXHVjZTVjXHVhZDZjXHViMjk0IFx1YmQ4NFx1YjE3OFx1ZDU1OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YmFiYiBcdWJjMWJcdWIyOTQgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YjljZVx1YzU0NFx1YzljOCBcdWMyMThcdWI4NWQgXHViMzU0XHVjNmIxIFx1YmQ4NFx1YjE3OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4MFx1Yjc4ZFx1YWM4Y1x1YjNjNCBcdWQwZGRcdWQ3NmNcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1YmQ4NFx1YjE3OFx1Yjk3YyBcdWMyMThcdWNlNThcdWQ2NTQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWJhYmIgXHViYzFiXHViMjk0IFx1YzBhY1x1ZDBkNSBcdWFjMWNcdWMyMThcdWM3NTggXHVjODFjXHVhY2YxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwZGRcdWQ3NmNcdWM3NTggXHVjZTVjXHVhZDZjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgMzJcdWFjMWNcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWQwZDVcdWM3NDQgMjlcdWFjMWMgXHViYzFiXHVjNTQ0IDNcdWFjMWNcdWI5N2MgXHViYzFiXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVhZGY4XHVjNzU4IFx1YmQ4NFx1YjE3OFx1YjI5NCAzXHVjNzU4IFx1YzgxY1x1YWNmMSA5XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGRkXHVkNzZjXHVhYzAwIFx1YmMxYlx1Yzc0MCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMTgsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0IFx1YmMxYlx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWQwZDVcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWM1YjQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1YmQ4NFx1YjE3OFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTc0IFx1YWRmOCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE0oMSAmbGU7Jm5ic3A7TSAmbGU7IDImdGltZXM7MTA8c3VwPjk8XC9zdXA+KVx1YzY0MCBOKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHViYzFiXHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxY1x1YzIxOFx1YjI5NCAyJnRpbWVzOzEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3M2NcdWJhNzAsIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc3NCBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTU4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQwIFx1ZDU2ZFx1YzBjMSBNXHVjNzQ0IFx1YjExOFx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBkZFx1ZDc2YyBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NTggXHViZDg0XHViMTc4XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgMjxzdXA+NjQ8XC9zdXA+XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMSlVUTkpBIiwiZGVzY3JpcHRpb24iOiI8cD5DaGlsZHJlbiBpbiBhIGtpbmRlcmdhcnRlbiBoYXZlIHJlY2VpdmVkIGEgbGFyZ2Ugc2FjayBjb250YWluaW5nIE0gY2FuZGllcy4gSXQgaGFzIGJlZW4gZGVjaWRlZCB0aGF0IHRoZSBjYW5kaWVzIGFyZSB0byBiZSBkaXN0cmlidXRlZCBhbW9uZyBOIGNoaWxkcmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNoaWxkIGhhcyBzdGF0ZWQgdGhlIG51bWJlciBvZiBjYW5kaWVzIHRoYXQgaXQgd2FudHMuIElmIGEgY2hpbGQgaXNuJnJzcXVvO3QgZ2l2ZW4gdGhlIGFtb3VudCBvZiBjYW5keSBpdCB3YW50cywgaXQgd2lsbCBnZXQgYW5ncnkuIEluIGZhY3QgaXQmcnNxdW87bGwgZ2V0IGFuZ3JpZXIgZm9yIGVhY2ggY2FuZHkgaXQgaXMgZGVwcml2ZWQgb2YuIFNvbWUgc3BlY3VsYXRlIHRoYXQgaXQmcnNxdW87cyBhbmdlciB3aWxsIGJlIGVxdWFsIHRvIHRoZSBzcXVhcmUgb2YgdGhlIG51bWJlciBvZiBjYW5keSBpdCBpcyBkZXByaXZlZCBvZi4gRm9yIGluc3RhbmNlLCBpZiBNaXJrbyBzdGF0ZXMgdGhhdCBoZSB3YW50cyAzMiBjYW5kaWVzIGJ1dCByZWNlaXZlcyBvbmx5IDI5LCBoZSB3b3VsZCBiZSBtaXNzaW5nIDMgY2FuZGllcywgc28gaGlzIGFuZ2VyIHdvdWxkIGJlIGVxdWFsIHRvIDkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHRoZXJlIGlzIGFuIGluc3VmZmljaWVudCBhbW91bnQgb2YgY2FuZHkgdG8gc2F0aXNmeSBhbGwgY2hpbGRyZW4uIFRoZXJlZm9yZSwgdGhlIGNhbmRpZXMgc2hvdWxkIGJlIGRpc3RyaWJ1dGVkIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgc3VtIG9mIHRoZSBjaGlsZHJlbiZyc3F1bztzIGFuZ2VyIGlzIG1pbmltYWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsIE0gKDEgJmxlOyBNICZsZTsgMiZtaWRkb3Q7MTA8c3VwPjk8XC9zdXA+KSBhbmQgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gaW50ZWdlcnMgKG9uZSBwZXIgbGluZSkgd2hpY2ggcmVwcmVzZW50IHRoZSB3aXNoZXMgb2YgdGhlIGNoaWxkcmVuLiBUaG9zZSBudW1iZXJzIGFyZSBhbGwgc3RyaWN0bHkgbGVzcyB0aGFuIDImbWlkZG90OzEwPHN1cD45PFwvc3VwPiwgYW5kIHRoZWlyIHN1bSBhbHdheXMgZXhjZWVkcyBNLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 못받은 사탕의 개수가 많아질수록 더 많은 분노가 생기기때문에 이를 최소화하기 위해선 못받은 사탕의 개수를 최소화하는 것이 중요하다.
- 따라서 모든 사람들을 대상으로 못 받는 사탕의 최대 개수를 기준으로 이진탐색을 진행하고 나머지 값에 대해선 최대힙에서 값을 뺀 뒤, 분노의 합을 구한다.

코드

# https://www.acmicpc.net/problem/2878
# 접근 방법
# 못받은 사탕의 개수가 많아질수록 더 많은 분노가 생기기때문에 이를 최소화하기 위해선 못받은 사탕의 개수를 최소화하는 것이 중요하다.
# 따라서 모든 사람들을 대상으로 못 받는 사탕의 최대 개수를 기준으로 이진탐색을 진행하고 나머지 값에 대해선 최대힙에서 값을 뺀 뒤, 분노의 합을 구한다.
import sys, heapq
input = sys.stdin.readline

m, n = map(int, input().split())
array = [int(input()) for _ in range(n)]
max_value = max(array)

start = 0
end = max_value
result = max_value
while start <= end:
    mid = (start+end)//2
    count = 0
    for x in array:
        count += max(x - mid, 0)
    if count <= m:
        result = min(result, mid)
        end = mid - 1
    
    else:
        start = mid + 1

q = []
for i in range(n):
    if array[i] > result:
        m -= array[i] - result
        array[i] = result
    heapq.heappush(q, -array[i])

while m > 0:
    x = -heapq.heappop(q)
    heapq.heappush(q, -(x-1))
    m -= 1

print(sum([x ** 2 for x in q]) % 2**64)