[BOJ 2878] 캔디캔디

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

2878번: 캔디캔디

- 문제 요약

 

택희는 M개의 사탕을 N명의 친구들에게 나누어 주려고 한다.

택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다.

만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 된다.

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

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

 

 

- 알고리즘 정리

 

각 친구들이 받고싶어하는 사탕의 개수보다 나눠주지 못하는 사탕의 개수가 작아야 효율적입니다.

=> min( i번째 사람이 받고 싶어하는 사탕의 개수, 남은 사탕 개수 / 남은 사람 수)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef unsigned long long ll;
ll m,n,arr[MAX],sum,result;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>m>>n;
	for(int i=0;i<n;i++){
		ll a;
		cin>>a;
		arr[i]=a;
		sum+=a;
	}
	sort(arr,arr+n);
	sum-=m;
	for(int i=0;i<n;i++){
		ll tmp=min(arr[i],sum/(n-i));
		result+=(tmp*tmp);
		sum-=tmp;
	}
	cout<<result;
}

코드 제출 결과