시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 464 | 169 | 139 | 43.849% |
서울과학고 기숙사에는 $N$개의 방이 일렬로 나열되어 있습니다. 교사들은 교내 방역을 위해 기숙사의 각 방에 진단 키트를 제공했습니다.
그러나 분배 과정에서 실수가 있었고, 방마다 받은 키트의 수가 다르게 되었습니다. 구체적으로, $i$번 방에서 받은 키트의 수는 $A_i$개입니다. 학생들은 이 상황을 해결하기 위해 키트를 서로 주고받기로 했습니다.
서로 멀리 떨어진 방끼리 키트를 주고받으면 소란스럽기 때문에, 키트는 인접한 방끼리만 주고받을 수 있습니다. 이때 한 방에서 인접한 다른 방으로 키트 한 개를 건네줄 때 혼잡도가 1 증가합니다. 당연하게도, 키트가 없는 방에서는 다른 방으로 키트를 건네줄 수 없습니다.
혼잡도가 너무 높으면 학생들이 벌점을 받을 수 있기 때문에, 학생들은 혼잡도를 최소로 하여 모든 방이 같은 수의 키트를 가지고 있도록 할 계획입니다. 이때 목표를 달성하기 위한 혼잡도의 최솟값을 구해 봅시다. 전체 키트의 수는 방의 수의 배수임이 보장됩니다.
첫 줄에는 방의 개수를 나타내는 정수 $N$이 주어집니다.
다음 줄에는 각 방이 초기에 받은 키트 수를 나타내는 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어집니다.
최소의 혼잡도를 출력합니다.
번호 | 배점 | 제한 |
---|---|---|
1 | 9 | 모든 $A_i$가 동일하다. |
2 | 16 | $A_i$들 중 최빈값은 $N-1$회 이상 등장한다. |
3 | 35 | $1 \le N \le 100$, $1 \le A_i \le 100$ |
4 | 40 | 추가 제한 조건이 없다. |
3 1 3 2
1
7 2 6 3 2 5 4 6
10
High School > 서울과학고등학교 > 2022 SciCom Qualification Test B번