2878번 캔디캔디

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

복습 생각 Greedy 그리디 탐욕 논리 필수 추천

어려운 문제였다. 

아래는 생각한 과정

1. 이분 탐색으로 해결하려 했으니, 생각해보니 mid의 기준을 정하는 것도 어려웠다. 사실 mid로 정할만한 것도 없는 것 같다.

2. 단순 정렬 후 앞에서부터 그냥 m을 각 원소에 맞게 빼면서 계산하면 되지 않을까 싶었는데 알고보니 이게 최적이 아니였다.

3. 몇 시간 동안 막히다가 결국 다른 분의 설명과 코드를 참고하였다. 참고한 블로그 - https://lyzqm.blogspot.com/2017/08/2878.html

무작정 정렬 후 앞에서부터 m을 깎는 것이 아니다.

예를 들어, m이 10이고, 캔디를 받을 사람이 3명이고 각각 1, 2, 11개의 사탕을 원한다고 하자.

10 3
1
2
11

정렬을 하면, 1 2 11이 될 것이고

10 - 1 = 9

9 - 2 = 7

이처럼 첫 번째, 두 번째 사람에겐 캔디를 모두 다 주면 7개가 남는다.

그리고 세 번째 사람에게 7개를 다 주어도 4개를 못 받기 때문에 분노는 4^2 = 16이 된다.

하지만 생각해보자.

한 사람에게만 몰두한다면 제곱이므로 숫자가 엄청 커질 것이다.

못 받는 사탕의 개수를 분배하면 어떨까?

위의 예제를 다시 생각해보자.

총 가지고 있는 사탕의 개수는 10개이고, 사람들이 원하는 사탕의 개수의 합은 14이다.

즉, 부족한 사탕은 정해져있다. 14 - 10 = 4개.(내 코드에서는 sum이 부족한 사탕의 개수)

부족한 사탕의 개수인 4개를 적절하게 배분하면 된다.

즉, 사탕을 많이 요구한 사람에게는 더 많이 주도록 한다. → 남은 사람으로 나누어 준다.((n-i)로 나누어 준다.)

rmd = (부족한 사탕의 개수) / (남은 사람의 수)

rmd는 해당 번째의 사람이 못 받는 사탕의 개수이다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
 
int n;
LL m;
vector<LL> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%lld %d", &m, &n);
 
    LL input, sum = -m;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &input);
        v.push_back(input);
        sum += input;
    }
 
    sort(v.begin(), v.end());
 
    LL answer = 0;
    for (int i = 0; i < n; i++) {
        LL rmd = min(v[i], sum / (n - i));
        answer += rmd*rmd;
        sum -= rmd;
    }
    
    printf("%lld\n", answer);
 
    return 0;
}