문제 15
코드포스합시다
정환이는 허무한 문제를 좋아한다. 그래서 허무한 문제를 내기로 했다.
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
$\displaystyle\sum_{i=1}^N B_i=0$을 만족하는 길이 $N$의 수열 $B$에 대해, $\displaystyle\sum_{i=1}^N \lvert A_i-B_i \rvert$의 최솟값을 구하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10\,000 \le A_i \le 10\,000)$
출력
첫 번째 줄에 $\displaystyle\sum_{i=1}^N \lvert A_i-B_i \rvert$의 최솟값을 출력한다.
예제 입력 1
5 3 1 4 1 5
예제 출력 1
14
예제 입력 2
6 -8 1 2 3 4 5
예제 출력 2
7
공식 해설
수열의 합을 $S=\sum_{i=1}^{N}A_i$라 하자. 합을 $0$으로 바꾸려면 원소들의 변화량의 합이 $-S$여야 하므로, 변화량의 절댓값의 합은 적어도 $\lvert S\rvert$이다. 식으로 쓰면
\[
\sum_{i=1}^{N}\lvert A_i-B_i\rvert
\ge\left\lvert\sum_{i=1}^{N}(A_i-B_i)\right\rvert
=\lvert S\rvert
\]
이다.
이 하한은 원소 하나만 바꾸어 달성할 수 있다. $B_1=A_1-S$로 두고 나머지는 $B_i=A_i$로 유지하면 합이 $0$이고 비용은 정확히 $\lvert S\rvert$이다.
따라서 입력을 읽으며 합을 누적하고 마지막에 절댓값을 출력한다. 시간복잡도는 $O(N)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
합을 long long 변수에 누적한 뒤 절댓값을 출력한다. 원소를 하나씩 읽으면 배열을 저장하지 않아도 된다.
C 구현
입력한 정수를 int 변수에 누적하고 마지막에 abs로 합의 절댓값을 구한다. 합의 절댓값은 최대 $2 \cdot 10^{9}$이므로 int로 충분하다.
Python 구현
읽은 정수를 합산한 뒤 합의 abs()를 출력한다. 입력량이 많으므로 sys.stdin.buffer를 사용한다.
Java 구현
입력값을 int 합에 누적한 뒤 Math.abs(sum)을 출력한다. 원소의 절댓값이 $10\,000$ 이하이고 합의 절댓값도 최대 $2 \cdot 10^{9}$이므로 int로 충분하다.
Rust 구현
입력값을 i32로 파싱하여 합산하고 마지막에 sum.abs()를 출력한다. 원소의 절댓값이 $10\,000$ 이하이고 합의 절댓값도 최대 $2 \cdot 10^{9}$이므로 i32로 충분하다. 원소 전체를 저장하지 않는다.
JavaScript 구현
수열의 합을 Number 변수 하나에 누적한 뒤 Math.abs(sum)을 출력한다.
$N\le200\,000$, $\lvert A_i\rvert\le10\,000$이므로 $\lvert S\rvert\le2\cdot10^9$이고 Number로 정확하다.