[PS] BOJ 32935 / 이상한 시행

문제 링크: https://www.acmicpc.net/problem/32935

난이도: 실버III

처음 맞닥뜨렸을 때는 방법이 떠오르지 않지만, 조금만 고민해보면 쉽게 풀이할 수 있는 문제였습니다.

문제

길이가 \(N\)인 수열 \(a\)가 주어진다. 다음의 시행을 원하는 만큼 하여 \(a\)의 원소들의 합을 최대로 하려한다. 그 최댓값을 구하여라.

• 현재 \(a\)의 원소들의 합을 \(N\)라고 하자. \(1 \le i \le N\)인 \(i\)를 하나 골라 \(a\)의 값을 \(−S\)로 바꾼다.

단, 어떤 상황에서도 답이 무한대가 아님을 보일 수 있다.

입력

첫 번째 줄에 수열의 크기를 나타내는 정수\(N\)이 주어진다.

• \(1 \le N \le 300,000\) 

두 번째 줄에 \(a_1, a_2, \cdots, a_N\)가 공백으로 구분되어 주어진다.

• \(−10^{9} \le a_i \le 10^{9}\)

풀이

🔎 엄밀한 증명은 아니며, 그저 풀이 과정에서 생각했던 내용을 정리해 둔 것입니다!

\(a_1, a_2, \cdots, a_N\) 에서 1회 시행을 통해 원소를 바꾸는 과정을 알아보자.

임의의 \(a_i\)를 \(x\), \(S = \displaystyle\sum_{i=1}^{N} a_i\) 라고 하자.
1회 시행 이후, x를 -S로 바꾸게 된다. 이때의 수열의 합을 \(S_1\)이라 하면,
\(S_1 = \displaystyle\sum_{i=1}^{N} a_i -x + (-S) = S - x - S = -x\),
따라서, 1회 시행 이후의 합은 -x가 된다.

2회 시행한 뒤의 결과를 보자.
이번에 바꾸게되는 임의의 원소 \(a_i\)를 \(y\)라 할때, \(y\)는 지난 1회 시행 이후의 수열의 합인 \(-S_1 = x\)로 바꾸게 되며, 이때의 합 \(S_2\)은 \(S_2 = S_1 -y +x = S - x - S - y + x = -y\)가 된다.

일반화하면, \(N\)회 시행 이후 원소 합 \(S_N\)은 이번 시행에 바꾼 원소를 \(a_N\)이라 할 때, \(S_N = -a_N\)이다.
따라서, 1회 이상 시행했을 경우의 최댓값은 수열 a의 원소 중 \(|a_i|\)가 가장 크며 음수인 원소를 바꾼 경우가 된다.

하지만, 문제의 조건에서 '이 시행을 원하는 만큼 수행할 수 있다' 고 명시하고 있으니, 아예 시행하지 않고 처음 수열의 합을 그대로 사용할 수도 있다. 따라서 초기 수열의 합과 1회 시행한 뒤의 수열의 합을 잘 비교해서 답으로 출력해야 한다.

코드

from sys import stdin

N = int(stdin.readline().strip())
array = list(map(int, stdin.readline().strip().split()))
S = sum(array)
array.sort()
S_2 = -array[0]
print(S_2 if S_2 > S else S)