한 부유한 사업가는 자녀들에게 재산을 증여하려고 한다.
재산은 일렬로 놓인 N개의 금고에 보관되어 있으며, i번째 금고에는 Ai원의 재산이 들어 있다.
사업가는 증여의 형평성을 맞추기 위해 다음 연산을 원하는 만큼 수행할 수 있다.
- 인접한 두 금고
i,i+1을 선택한다. i번째 금고에서1원을 꺼내i+1번째 금고에 넣는다.- 즉,
Ai는1감소하고A(i+1)는1증가한다.
돈은 왼쪽에서 오른쪽으로만 이동할 수 있다.
모든 자녀가 동일한 금액을 받도록, 즉 모든 금고의 금액을 같게 만들 수 있는지 판단하고, 가능하다면 필요한 최소 이동 횟수를 구하여라.
첫째 줄에 금고의 개수 N이 주어진다.
둘째 줄에 각 금고에 들어 있는 금액 A1, A2, ..., AN이 공백으로 구분되어 주어진다.
모든 금고의 금액을 같게 만드는 것이 불가능하면 -1을 출력한다.
가능하다면 필요한 최소 이동 횟수를 출력한다.
1 ≤ N ≤ 300,0000 ≤ Ai ≤ 10^9
5
5 1 3 2 4
4
1 2 3 5
4
-1
전체 금액은
5 + 1 + 3 + 2 + 4 = 15
이며,
15 / 5 = 3
이므로 모든 금고를 3원으로 만드는 것이 가능하다.
왼쪽부터 살펴보면,
| 위치 | 현재 누적 합 | 목표 누적 합 | 초과 금액 |
|---|---|---|---|
| 1 | 5 | 3 | 2 |
| 2 | 6 | 6 | 0 |
| 3 | 9 | 9 | 0 |
| 4 | 11 | 12 | -1 |
첫 번째 금고에서 2원을 오른쪽으로 이동시키고,
마지막에는 네 번째 금고가 1원 부족하므로 이전 금고에서 1원이 이동해야 한다.
총 이동 횟수는
|2| + |0| + |0| + |−1| = 4
이다.
전체 금액은
1 + 2 + 3 + 5 = 11
이며,
11 % 4 ≠ 0
이므로 모든 금고를 같은 금액으로 만드는 것은 불가능하다.
따라서 정답은
-1
이다.
모든 금고의 금액이 같아지려면 최종 금액은
target = (A1 + A2 + ... + AN) / N
이어야 한다.
총합이 N으로 나누어떨어지지 않으면 답은 -1이다.
가능한 경우, i번째 위치까지의 누적 합을 prefix라고 하자.
i번째 위치까지의 금고들이 최종적으로 가져야 하는 금액은
target × i
이다.
따라서
diff = prefix - target × i
는 i번째 위치까지의 구간이 오른쪽으로 보내야 하거나, 오른쪽에서 받아야 하는 금액을 의미한다.
인접한 금고 사이를 지나가는 금액은 반드시 한 번씩 이동해야 하므로,
필요한 최소 이동 횟수는
Σ |diff|
(i = 1부터 N-1까지)
가 된다.
배열을 한 번만 순회하므로 시간 복잡도는
O(N)
이며,
추가 공간은 거의 사용하지 않으므로 공간 복잡도는
O(1)
이다.
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
if total % N:
print(-1)
sys.exit()
target = total // N
answer = 0
prefix = 0
for i in range(N - 1):
prefix += A[i]
diff = prefix - target * (i + 1)
answer += abs(diff)
print(answer)