[Baekjoon 25945] 컨테이너 재배치 - JAVA

[Silver III] 컨테이너 재배치 - 25945

문제 링크

성능 요약

메모리: 87460 KB, 시간: 464 ms

분류

그리디 알고리즘, 수학, 정렬

문제 설명

항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 n$n$개가 그려져 있고, 현재 하치장에는 총 m$m$개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 1$1$로 동일하며, 각 칸에 쌓을 수 있는 컨테이너의 개수에는 제한이 없다. 즉, ai$a_i$ (1≤i≤n$1 ≤ i ≤ n$)가 현재 i$i$번째 칸에 쌓여있는 컨테이너의 개수를 나타내면, m=∑i=1nai$m = \sum_{i=1}^{n}{a_i}$의 관계가 만족된다.

현재와 같이 높이에 아무 제한이 없이 컨테이너가 쌓여 있을 경우 각 칸별로 쌓여있는 컨테이너의 개수의 차이가 심하여 안전상 문제점을 유발할 수 있기 때문에, 일부 컨테이너를 크레인을 이용하여 다른 칸으로 옮겨서 각 칸의 높이 차이가 1$1$이하가 되도록 재배치하고자 한다. 즉, 임의의 i$i$, j$j$에 대해 |ai−aj|≤1$\left| a_i - a_j \right| ≤ 1$ 이 만족되어야 한다. 컨테이너는 한번에 한 개씩만 옮길 수 있고 옮기는 거리에 따른 추가 비용은 없다고 가정한다.

예를 들어 그림 1 과 같이 35$35$개의 컨테이너가 8$8$개의 칸에 쌓여 있을 경우 m=35$m = 35$, n=8$n = 8$에해당한다. 이를 높이 차이가 1$1$이하가 되도록 재배치하면 그림 2 와 같은 결과를 얻을 수 있고, 이경우 5$5$개의 컨테이너를 옮겨야 한다.

그림 1. 재배치 이전	그림 2. 재배치 결과

입력으로 각 칸에 초기에 쌓여 있는 컨테이너의 높이 a1,a2,…,an$a_1, a_2, \dots , a_n$이 주어질 때, 임의의 i$i$, j$j$에 대해 |ai−aj|≤1$\left| a_i - a_j \right| ≤ 1$ 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 컨테이너를 쌓을 수 있는 칸의 개수를 나타내는 양의 정수 n$n$ (1≤n≤106$1 ≤ n ≤ 10^6$)이 주어진다. 다음 줄에는 현재 각 칸에 쌓여 있는 컨테이너의 개수 ai$a_i$를 나타내는 n$n$개의 0$0$이상의 정수들이 주어지고, 컨테이너의 총 개수 m$m$ 은 1≤m≤2×109$1 ≤ m ≤ 2 \times 10^9$ 으로 제한한다.

출력

출력은 표준출력을 사용한다. 문제의 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 한 줄에 출력한다.

문제풀이

양옆에 붙어있는 컨테이너끼리는 +- 1의 차이까지만 허용된다.

위 조건이 성립하도록 다시 정렬한 후 i번째 칸의 컨테이너 개수를 $b_i$라 한다면 정수$x$가 존재하고, $i$번째의 경우 아래 식이 성립한다.

($b_i=x, x + 1$)

즉, 부등식으로 만들어보면 아래와 같은 식이 완성된다.

$$nx=\sum_{i=1}^{n}x\le\sum_{i=1}^{n}b_i=\sum_{i=1}^{n}a_i=m<\sum_{i=1}^{n}(x+1)=n(x+1)$$

• $nx \le \sum_{i=1}^{n}b_i$: $nx$는 $x$를 모든 위치에 적용한 경우의 최소 컨테이너 개수다.
  = 모든 $b_i$의 합보다 작거나 같아야 한다.
• $\sum_{i=1}^{n}b_i \le \sum_{i=1}^{n}a_i = m$: $b_i$의 합은 원래 배열 $a_i$의 합인 $m$보다 작거나 같아야 한다.
  = 새로운 배열의 총 컨테이너 개수가 원래 배열과 같거나 작아야 함을 의미한다.
• $\sum_{i=1}^{n}b_i < \sum_{i=1}^{n}(x+1) = n(x+1)$: $b_i$의 합은 $x$를 모든 위치에 적용한 경우의 최대 컨테이너 개수 $n(x+1)$보다 작아야 한다.
  = $x+1$은 각 위치에 허용된 최대 컨테이너 개수다.

위 부등식을 바탕으로 예제 그림을 쉽게 이해해보자

문제에 나와있는 예제이다.

빨간색 선(X + 1)을 초과한 컨테이너를 파란색 선(X) 미만이어서 빈 공간에 이동시켜주면 된다.

cnt1을 빨간색 컨테이너, cnt2를 파란색 컨테이너에 저장하는 용도의 변수로 사용했다.

$a_i$가 X + 1보다 크다면 cnt1의 초과한 $a_i - x - 1$을 더했고, x보다 작다면 cnt2에 $x - a_i$를 더했다.

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));
        int n = Integer.parseInt(br.readLine());

        int[] container = new int[n];
        int cnt1 = 0, cnt2 = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            container[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        for (int i : container) {
            sum += i;
        }

        int avg = sum / n;

        for (int i : container) {
            if (i > avg + 1) {
                cnt1 += (i - avg - 1);
                } else if (i < avg) {
                cnt2 += (avg - i);
            }
        }

        System.out.println(Math.max(cnt1, cnt2));
    }
}

코드풀이

int n = Integer.parseInt(br.readLine());
int[] container = new int[n];
int cnt1 = 0, cnt2 = 0;

for (int i = 0; i < n; i++) {
    container[i] = Integer.parseInt(st.nextToken());
}

• n: 컨테이너를 쌓을 칸의 개수
• container: 컨테이너의 층 수를 입력받을 배열
• cnt1, cnt2: 초과하거나, 미달한 컨테이너들을 저장할 변수

int sum = 0;
for (int i : container) {
    sum += i;
}

int avg = sum / n;

• sum: 컨테이너의 총 개수를 저장할 배열
• for-each를 사용해 배열 container의 모든 요소를 더해 sum 변수에 저장한다.
• 컨테이너의 총 개수인 sum을 배열의 길이 n으로 나눠 평균값 avg를 계산한다.

for (int i : container) {
    if (i > avg + 1) {
        cnt1 += (i - avg - 1);
    } else if (i < avg) {
        cnt2 += (avg - i);
    }
}

• 컨테이너의 각 칸마다 avg + 1보다 크면 cnt1에 (i - avg - 1)을 더한다.
• 컨테이너의 각 칸이 avg보다 작으면 cnt2에 (avg - i)를 더한다.
  평균 이상과 평균 이하의 요소를 구분해서 카운트하기 위함이다.

System.out.println(Math.max(cnt1, cnt2));

• cnt1과 cnt2 중 더 큰 값을 출력한다.