[Greedy Algorithm] BOJ2878 - 캔디캔디

문제

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

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

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

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

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

---

입력예제

5 3
1
3
2

 

출력예제

1

---

진짜 오래 붙잡고 있었다. 나는 실버까지 밖에 되지 못하는 건가 하고 망연자실했던 골드 문제다 하하하

그래서 결국 같은 스터디원에게 어떻게 풀었는지 물어보았다.

​

여기서 가장 최적이 무엇인가를 고려하는 문제이다.

첫번째, 무조건 큰 수부터 사탕을 주는 것이 최적이다 -> 실패

두번째, 받지 못하는 사탕의 개수가 고르게 분포되는 것이 최적이다 -> 성공

 

10 3
6
5
4

3명에게 10개의 사탕을 나누어 줄 수 있고 각각 6, 5, 4개의 사탕을 가지고 싶어한다. 이 때, 가지고 싶어하는 사탕의 총 개수는 15개이고 이를 15-10을 하게 되면 5개가 모자란다. 이것을 각각 2, 2, 1로 공평하게 분배해주면 최소의 분노를 가질 수 있다.

하지만 이게 전부가 아니라 아래의 한 가지 사실을 더 고려해야 한다. 이거 생각 못해서 시간을 다 잡아먹었다. 냠냠

10 3
8
7
1

여기서 모자라는 사탕의 개수는 16-10=6이 나온다. 6을 공평하게 분배하면 2, 2, 2인데 1개를 가지고 싶은 사람이 2개가 모자를 수 없다.. 이런 점을 고려하는 것이 이 문제의 핵심인 듯 하다 !!

 

---

소스코드

import sys
candy = 0
M, N = map(int, sys.stdin.readline().strip().split())
friend = sorted([int(sys.stdin.readline()) for _ in range(N)])

rest = sum(friend) - M # 나눠주지 못하는 사탕의 개수

answer = 0
for i in range(N):
  num = min(friend[i], rest // (N-i)) # 예외적인 상황을 고려한 코드
  answer += num * num
  rest -= num

print(answer % (pow(2,64)))

예외적인 상황을 고려한 코드는 다음과 같은데 나머지를 나누어주어야 한다는 것 이외에 사실 완벽하게 이해하지 못한 것 같다. 주변에 아는 사람이 있다면 꼭 알고 싶다

​

문제를 많이 풀어서 골드 문제도 후딱 생각할 수 있는 사람이 되어야지

​