25945번 - 컨테이너 재배치 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 960 | 406 | 324 | 42.023% |
문제
항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 $n$개가 그려져 있고, 현재 하치장에는 총 $m$개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 $1$로 동일하며, 각 칸에 쌓을 수 있는 컨테이너의 개수에는 제한이 없다. 즉, $a_i$ ($1 ≤ i ≤ n$)가 현재 $i$번째 칸에 쌓여있는 컨테이너의 개수를 나타내면, $m = \sum_{i=1}^{n}{a_i}$의 관계가 만족된다.
현재와 같이 높이에 아무 제한이 없이 컨테이너가 쌓여 있을 경우 각 칸별로 쌓여있는 컨테이너의 개수의 차이가 심하여 안전상 문제점을 유발할 수 있기 때문에, 일부 컨테이너를 크레인을 이용하여 다른 칸으로 옮겨서 각 칸의 높이 차이가 $1$이하가 되도록 재배치하고자 한다. 즉, 임의의 $i$, $j$에 대해 $\left| a_i - a_j \right| ≤ 1$ 이 만족되어야 한다. 컨테이너는 한번에 한 개씩만 옮길 수 있고 옮기는 거리에 따른 추가 비용은 없다고 가정한다.
예를 들어 그림 1 과 같이 $35$개의 컨테이너가 $8$개의 칸에 쌓여 있을 경우 $m = 35$, $n = 8$에해당한다. 이를 높이 차이가 $1$이하가 되도록 재배치하면 그림 2 와 같은 결과를 얻을 수 있고, 이경우 $5$개의 컨테이너를 옮겨야 한다.
| 그림 1. 재배치 이전 | 그림 2. 재배치 결과 |
입력으로 각 칸에 초기에 쌓여 있는 컨테이너의 높이 $a_1, a_2, \dots , a_n$이 주어질 때, 임의의 $i$, $j$에 대해 $\left| a_i - a_j \right| ≤ 1$ 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 컨테이너를 쌓을 수 있는 칸의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 10^6$)이 주어진다. 다음 줄에는 현재 각 칸에 쌓여 있는 컨테이너의 개수 $a_i$를 나타내는 $n$개의 $0$이상의 정수들이 주어지고, 컨테이너의 총 개수 $m$ 은 $1 ≤ m ≤ 2 \times 10^9$ 으로 제한한다.
출력
출력은 표준출력을 사용한다. 문제의 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 한 줄에 출력한다.
예제 입력 1
4 1 2 3 3
예제 출력 1
1
예제 입력 2
8 5 6 7 2 3 4 2 6
예제 출력 2
5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호