[BOJ 2878 🥇2] 캔디캔디 (Python)

https://www.acmicpc.net/problem/2878

2878번: 캔디캔디

문제

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

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

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

5 3
1
3
2

 

예제 출력 1 

1

 

예제 입력 2 

10 4
4
5
2
3

 

예제 출력 2 복사

4

⭕ CODE

import sys

sys.stdin = open('input.txt')

input = sys.stdin.readline

m,n = map(int,input().split())

arr = []

for _ in range(n):
    candy = int(input())
    arr.append(candy)

arr.sort()

# 못 받은 사탕 수
na = sum(arr) - m

# 분노의 합
result = 0

for i in range(n):
    # 받고 싶어하는 사탕의 수 와 남은 분노를 남은 사람수로 n빵하는것과 비교
    # 작은것을 택한다
    a = min(arr[i], na // (n-i))

    # 분노 더해주기
    result += a**2

    # 나머지에서 a만큼 빼준다.
    na -= a

print(result % 2**64)

✏️ Comment

친구들이 받고 싶어하는 사탕의 개수의 합은 항상 m을 넘는다. 그러므로 무조건 나머지가 생긴다. 나머지를 분노의 합이 최소가 되도록 나누려면 최대한 공평하게 나누어야 무조건적으로 최소가 된다. n빵은 불가능 n빵 계산과 받고 싶어하는 것 중 작은것을 고르면 최소가 된다.