문제 해설
Difficulty : *800 (Greedy / Math)
폴리카프가 n명의 친구에게 사탕을 똑같이 나눠주려 합니다. 친구들은 이미 사탕을 가지고 있고, 모두 똑같은 수로 다시 나누어 주기 위해서 최소 k명의 사탕을 재분배해야 합니다. 예를 들어 n = 4, 각 친구들이 가지고 있는 사탕의 수는 a = [4, 5, 2, 5] 일 때, 사탕을 5개씩 가지고 있는 두 번째, 네 번째 친구의 사탕만 세 번째 친구에게 분배해주면 됩니다. 이때 고른 친구의 수는 두 명, 즉 k의 최솟값은 2입니다. 입력을 받은 후 k의 최솟값을 출력하며, 만약 똑같이 나누어 줄 수 없을 시 -1을 출력합니다.
풀이
먼저 전체 사탕의 수를 n명의 친구에게 똑같이 나누어 줄 수 있는지 검사합니다. 똑같이 나눠줄 수 있다면 나눈 값보다 큰 수를 가지고 있는 친구는 무조건 재분배를 해야 합니다. 전체 값에 대해 비교하며 k를 정할 수 있습니다.
코드
C
#include <stdio.h>
int main(){
int t, n, i, j, sum = 0, count= 0;
int arr[200001];
for(i = 0; i<200001;i++){
arr[i] = 0;
}
scanf("%d", &t);
for(i = 0; i < t; i++){
scanf("%d", &n);
for(j = 0; j < n; j++){
scanf("%d", &arr[j]);
sum += arr[j];
}
if (sum % n == 0) {
for(j = 0; j < n; j++){
if(arr[j] > sum/n){
count++;
}
}
printf("%d\n", count); //result print
}else{
printf("-1\n"); //impossible
}
count = 0;
sum = 0;
}
return 0;
}
C++
#include <bits/stdc++.h>
using namespace std;
long long t,n,arr[200005];
int main(){
cin >> t;
for (int i = 0; i < t; i++){
cin >> n;
int sum=0;
int count=0;
for (int j = 0; j < n; j++){
cin >> arr[j];
sum += arr[j];
}
if (sum%n == 0){
for (int j = 0; j < n; j++){
if (arr[i]> sum/n){
count++;
}
}
cout << count << "\n"; //result print
}
else{
cout << -1 << "\n"; //impossible
}
}
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++) {
int n = sc.nextInt();
int arr[] = new int[n];
int sum = 0;
int count = 0;
for (int j = 0; j < n; j++) {
arr[j] = sc.nextInt();
sum += arr[j];
}
if (sum % n == 0) {
for (int j = 0; j < n; j++) {
if (arr[j] > sum / n) {
count++;
}
}
System.out.println(count); //result print
} else {
System.out.println(-1); //impossible
}
}
}
}
Python
t = int(input())
for i in range(t):
n = int(input())
arr = list(map(int,input().split()))
asum = sum(arr)
count = 0
if sum(arr)%n == 0:
for j in range(n):
if arr[j] > asum//n:
count += 1
print(count) # result print
else:
print('-1') # impossible