문제
오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다.
택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다.
놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다.
예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다.
택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 최소화해 그 값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 M(1 ≤ M ≤ 2×10^9)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×10^9보다 작으며, 친구들이 받고 싶어하는 사탕의 개수의 합은 항상 M을 넘는다.
출력
첫째 줄에 택희 친구들의 분노의 합의 최솟값을 264로 나눈 나머지를 출력한다.
엠제이랑 하수구 냄새나는 공원 바닥에서 같이 읽은 문제다.
풀지는 않고 각자 집에가서 풀었는데, 또 나만 못풀어.. 또.. 나만..
그리디 문제인건 알고 있었고, 어떻게 풀어야하는지도 알았다!!!
가지고있는 사탕(M) - 받고싶어하는 사탕 총 합 을 사람들에게 최대한 고르게 나눠주면 되는 문제였다.
문제는 모자란 사탕 개수를 고르게 나눠줄 때, 사람마다 그 수를 받고싶어했던 사탕의 수보다는 크게 할 수 없어서 그걸 어떻게 분배해야할지 모르겠는거다.
이걸 코드로 구현하지 못하겠어서 다른 방법으로 시도했다. 그냥 문제 그대로 M이 0이 될 때까지 반복문으로 나눠줬었다. 아닌 것 같은데도 이거밖에 생각이 안나니까.. 어쩔수없이 대충 답이 나오길래 제출했지만 당연히 시간초과가 났다. 슬펐다
틀린코드 (시간초과)
M, N = map(int, input().split())
wants = []
for _ in range(N):
wants.append(int(input()))
wants.sort(reverse=True)
i = 0
while M:
if i < N-1 and wants[i] == wants[i+1]:
i += 1
for j in range(i+1):
wants[j] -= 1
M -= 1
if not M:
break처음에는 이런식으로
받고싶어하는 사탕개수가 많은 순서대로 사탕을 나눠주고
그 과정에서 매번 그 다음 사람과 더 받고 싶은 사탕 개수가 같아졌는지 검사를 했었다.
나랑 비슷하게 푼 사람도 있었는데 그 사람은 어떻게 시간초과에 안걸렸는지 모르겠다.
이러고 모르겠어서 그냥 누웠는데 엠제이와 전화하다가 우울해하니까 줌으로 내 코드를 봐준 거다.
그리디하게 하려면 어떻게 해야했을까?
내가 고민했던 부분: 당연히 받고싶은 사탕 개수보다 못 나눠주는 사탕 개수가 적어야하는데, 이걸 어떻게 구현?
👉🏻 남은 수의 개수(cant) // 남은 사람 명수 를 바로 쓰는게 아니라, min(그 사람이 받고싶어했던 개수, 남은 cant // 남은 명수) 로 얼만큼 분배해줄지 정하는 것!!!!
M, N = map(int, input().split())
wants = []
for _ in range(N):
wants.append(int(input()))
wants.sort()
cant = sum(wants) - M
ans = 0
for i in range(N):
tmp = min(wants[i], cant // (N-i))
ans += tmp**2
cant -= tmp
print(ans % 2**64)문제도 제대로 안 읽어서 나머지로 출력해야하는데 그거때문에 계속 틀리고 아무튼 결국엔 맞았다. 행복했다
