[BOJ 2878 // C++] 캔디캔디

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2878번 문제인 캔디캔디이다.
문제는 아래 링크를 확인하자.

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

2878번: 캔디캔디

사탕을 하나 주는 것으로 친구들의 분노수치의 합을 가장 많이 줄이려면 원하는 사탕의 수가 지금 가장 많은 친구에게 사탕을 줘야 함을 관찰하자. 이를 M회 반복하면 문제를 해결할 수 있겠지만 그러기에는 M으로 매우 큰(20억) 입력이 주어질 수 있으므로 사탕을 하나하나 분배하는 것으로는 문제를 충분히 해결할 수 없다.

 

수식을 이용해 위 과정에서 반복되는 과정을 최적화시켜 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;

int N; ll M;
ll arr[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	for (int i = N - 1; i > 0; i--) {
		ll cnt = N - i;
		if (M >= cnt * (arr[i] - arr[i - 1])) M -= cnt * (arr[i] - arr[i - 1]);
		else {
			ll x = M / cnt, r = M % cnt;
			ll ans = r * (arr[i] - x - 1) * (arr[i] - x - 1) + (cnt - r) * (arr[i] - x) * (arr[i] - x);
			for (int j = i - 1; j > -1; j--) ans += arr[j] * arr[j];

			cout << ans;
			return 0;
		}
	}

	ll x = M / N, r = M % N;
	ll ans = r * (arr[0] - x - 1) * (arr[0] - x - 1) + (N - r) * (arr[0] - x) * (arr[0] - x);

	cout << ans;
}