24938번 : 키트 분배하기

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

24938번: 키트 분배하기

 

 

문제

서울과학고 기숙사에는 N개의 방이 일렬로 나열되어 있습니다. 교사들은 교내 방역을 위해 기숙사의 각 방에 진단 키트를 제공했습니다.

그러나 분배 과정에서 실수가 있었고, 방마다 받은 키트의 수가 다르게 되었습니다. 구체적으로, i번 방에서 받은 키트의 수는 Ai개입니다. 학생들은 이 상황을 해결하기 위해 키트를 서로 주고받기로 했습니다.

서로 멀리 떨어진 방끼리 키트를 주고받으면 소란스럽기 때문에, 키트는 인접한 방끼리만 주고받을 수 있습니다. 이때 한 방에서 인접한 다른 방으로 키트 한 개를 건네줄 때 혼잡도가 1 증가합니다. 당연하게도, 키트가 없는 방에서는 다른 방으로 키트를 건네줄 수 없습니다.

혼잡도가 너무 높으면 학생들이 벌점을 받을 수 있기 때문에, 학생들은 혼잡도를 최소로 하여 모든 방이 같은 수의 키트를 가지고 있도록 할 계획입니다. 이때 목표를 달성하기 위한 혼잡도의 최솟값을 구해 봅시다. 전체 키트의 수는 방의 수의 배수임이 보장됩니다.

 

 

입력

첫 줄에는 방의 개수를 나타내는 정수 N이 주어집니다.

다음 줄에는 각 방이 초기에 받은 키트 수를 나타내는 정수 A1, A2, ⋯, An이 공백을 사이에 두고 주어집니다.

 

 

출력

최소의 혼잡도를 출력합니다.

 

 

제한

ㅁㅁ

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        long arr[] = new long[n];
        long sum = 0;
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
        }
        
        long r = sum / n;
        long result = 0;
        for (int i = 0; i < n - 1; i++) {
            if(arr[i]>=r) {
                arr[i + 1] += (arr[i] - r);
                result += (arr[i] - r);
            } else {
                arr[i + 1] -= (r - arr[i]);
                result += (r - arr[i]);
            }
        }
        
        System.out.println(result);
    }
}

 

 

해결방법

결국 모든 키트의 수를 일정하게 나눠야 하기 때문에 [키트의 개수 / 방의 개수] 결과 값(R)으로 분배되어야 한다.

단순히 1번방이 R보다 작다면 인접한 2번방에서 필요한 만큼 받으면 되고, R보다 크다면 큰만큼 2번방에게 건네주면 된다. 이를 n-1번 반복하면 된다.

 

1번방이 R보다 작다 => 결국 어디선가 받아야 한다.

1번방이 R보다 크다 => 결국 누군가에게 넘기긴 해야한다.

 

예제2

7
2 6 3 2 5 4 6
4 4 3 2 5 4 6 => 혼잡도 2 증가
4 4 3 2 5 4 6 => 혼잡도 0 증가
4 4 4 1 5 4 6 => 혼잡도 1 증가
4 4 4 4 2 4 6 => 혼잡도 3 증가
4 4 4 4 4 2 6 => 혼잡도 2 증가
4 4 4 4 4 4 4 => 혼잡도 2 증가
총 혼잡도 => 10