[SWEA] 5603. [Professional] 건초더미

문제

크기가 다른 n개의 건초더미가 있을 때, 이 건초더미들을 모두 같은 크기로 만드려고 한다.

 

최소 몇번을 움직여야 모두 같은 크기로 만들 수 있는 지 구하는 문제

 

풀이방법

1) 모든 건초더미의 합으로 평균을 구한다. n개의 건초 더미들은 평균과 같은 크기가 되어야한다.

 

2) 평균과 각 건초더미들의 차를 구한다.

 

3) 평균과 각 건초더미의 차의 합 / 2는 건초더미가 움직여져야할 최소한의 숫자이다.

한 번 옮길 때마다 두 개의 건초더미가 평균에 가까워지기 때문이다.

 

소스코드

package samsung;

import java.util.*;

public class s_5603 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int[] a = new int[n];
			int sum = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				sum += a[i];
			}
			
			int b = sum / n;
			int diff = 0;
			for(int i = 0; i < n; i++) {
				diff += Math.abs(b - a[i]);
			}
			
			System.out.println("#" + t + " " + diff/2);
		}
	}
}