NYPC 2021 예선 | 파티

[문제]

 

기말 시험이 끝난 N 명의 친구들은 파티를 하기로 했다. 파티에 필요한 음식과 물품들을 사기 위해 각자 미리 돈을 사용했다. 친구들은1번부터 번까지 번호가 붙어 있다고 하자. 친구들 중 i 번째 친구가 사용한 돈은 Mi​원이다.

친구들의 부담을 동일하게 하기 위해 파티 후에 서로 돈을 주고받아 사용한 금액이 같도록 하려고 한다. 금액이 정확히 나누어 떨어지지는 않을 수 있으므로, 돈을 가장 많이 사용한 친구와 가장 적게 사용한 친구의 금액 차이가 1인 것까지는 허용한다.

3 명의 친구 A, B, C가 파티를 하였고, 각자 사용한 금액이 6000원, 3000원, 1000원이라고 하자. 아래 그림처럼 B가 A에게 334원, C가 A에게 2333원을 주면 각자 사용한 금액이 A는 3333원, B는 3334원, C는 3333원이 되어 위의 조건을 만족한다. (아래 그림에서 네모 안은 사용한 금액, 화살표 위는 전달한 금액이다. 전달받은 금액만큼 사용한 금액이 줄어드는 것으로 생각하면 된다.)

<그림 1> 총 전달 금액 2667원 예시

위 <그림 1>의 경우 전달된 금액은 모두 334+2333=2667원이다.

아래 <그림 2>와 같이 하면 조건을 만족하면서 전달된 금액을 2666원으로 줄일 수 있다.

<그림 2> 총 전달 금액 2666원 예시

N 명의 학생이 처음에 사용한 금액들을 입력으로 받아 조건을 만족하도록 돈을 주고받을 때 가능한 최소의 전달된 금액을 계산하는 프로그램을 작성하라.

 

 

[입력 형식]

 

첫 줄에 친구들의 수를 나타내는 정수 N이 주어진다. (2≤N≤200000)

둘째 줄에 음이 아닌 정수 M1​, M2​, ……, MN​이 공백을 사이에 두고 주어진다. (M1​+M2​+⋯+MN​≤10^15)

 

 

[출력 형식]

 

전달된 금액의 가능한 최솟값을 출력한다.

 

 

[해설]

 

전체 사용 금액의 평균에 맞추는 것이 목표임은 자명하므로 주고받는 금액을 최소화할 수 있도록 1 차이인 경우들을 잘 고려해 주면 됩니다. (그리디)

 

 

[C/C++]

 

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

#define MAX 200001
typedef long long ll;
int n;
ll arr[MAX],sum,result;

ll f(ll x){
	if(x<0){
		return -x;
	}
	return x;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		sum+=arr[i];
	}
    sort(arr,arr+n,greater<ll>());
    for(int i=0;i<n;i++){
    	if(i<sum%n){
    		result+=f(arr[i]-sum/n-1);
		}
		else{
			result+=f(arr[i]-sum/n);
		}
	}
	cout<<result/2;
}