문제
간식 시간이 되어 N명의 학생들이 일렬로 앉아 간식을 먹고 있다. 그런데 일부 욕심쟁이 학생들이 간식을 많이 갖고 갔기 때문에 선생님이 간식을 똑같이 나누려고 한다.
선생님이 간식을 가져가는 것은 학생들이 원치 않기 때문에 학생들끼리 간식을 옮기려고 한다. 각 학생은 자신이 갖고 있는 간식의 일부를 자신의 옆 사람 중 한 명에게 줄 수 있다.
간식을 주고받는 일은 번거롭기 때문에 가능한 한 이런 일을 최소화하려고 한다. 초기 상태의 정보가 주어질 때 간식을 옮기는 횟수를 최소화하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 학생의 수 N이 주어진다. (2 ≤ N ≤ 100,000)
두 번째 줄에는 각 학생이 갖고 있는 간식의 수 Sk가 주어진다.
학생의 정보는 왼쪽에서 오른쪽 방향으로 주어지며, 총 간식의 수는 N의 배수임에 유의하여라. (0 ≤ Sk ≤ 1,000) 전체 데이터의 60%는 N ≤ 1,000이다.
출력
간식을 옮기는 횟수의 최솟값을 출력한다.
예제 #1
3
1 3 5
2
3번째 학생이 2번째 학생에게 2의 간식을 준 후, 2번째 학생이 1번째 학생에게 2의 간식을 주면 된다.
예제 #2
10
10 13 26 11 15 12 18 13 25 7
6
출처
2015 정보올림피아드 지역예선 변형
로그인해야 코드를 작성할 수 있어요.