[백준] 2878 - 캔디캔디

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

2878번: 캔디캔디

 

분노의 합(제곱수의 합)을 최소화하기 위해서는 각 제곱수를 최소화해야 한다.

5^2 > 1^2 + 1^2 + 1^2 + 1^2 + 1^2 이런 식으로 제곱 수를 최대한 분할해야 최솟값을 구할 수 있다.

 

그렇다면 사탕의 개수를 오름차순으로 정렬한 후에 작은 것부터 나눠주면 된다고 생각할 수 있다.

하지만 이렇게 하면 다음과 같은 반례가 생긴다.

4 3
1 2 7

이 경우 답은 14(= 1^2 + 2^2 + 3^2) 이지만, 작은 것부터 나눠주면

남은 사탕의 개수는 0 0 6개여서 분노의 합은 36이 돼버리고 만다.

 

이 문제를 해결할 방법은 바로 모자라는 사탕을 고르게 분배하는 것이다. 무슨 말이냐면,

위의 예제에서 필요한 사탕은 10, 가지고 있는 사탕은 4, 따라서 모자란 사탕은 6이다.

이 6개의 모자란 사탕을 3명에게 고르게 분배하면 되는데, 첫 번째 친구는 1개의 사탕을 필요로 하므로 2개의 사탕을 줄 수 없다.

따라서 다음과 같은 식으로 나누어 주어야 한다.

long long k = min(a[i], sum / (n - i + 1));

 

이렇게 하면 처음 친구는 1개, 그다음은 2개, 그다음은 3개의 모자란 사탕이 생긴다.

 

#include <algorithm>
#include <iostream>
using namespace std;

long long a[100001];

int main() {
    long long m, n, sum = 0;
    cin >> m >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + n + 1);

    long long ans = 0;
    sum -= m;

    for (int i = 1; i <= n; i++) {
        long long k = min(a[i], sum / (n - i + 1));
        ans += k * k;
        sum -= k;
    }

    cout << ans;
}