백준 비드맨(19590)

비드맨

1. 힌트

1) 언제나 가장 많이 있는 구슬 종류 두 가지를 부딪히는 것이 이득입니다.

2) $max(S) \ge sum(S) - max(S)$라면 답은 자명합니다.

3) 위 조건을 만족하지 않으면 전체 합이 짝수면 모두 없앨 수 있고 홀수면 한 개가 남습니다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

단순하게 생각해 보면 부딪힐 때마다 한 번에 2개 씩 없어지니 짝수면 다 없앨 수 있고 홀수면 한 개가 남을 것 같습니다. 하지만 그 생각은 에제 입력 2에서 무너집니다.

그렇다면 손으로 직접 해보겠습니다. 예제 입력 3을 보니 $2$끼리 먼저 부딪히면 $4$가 남습니다. 하지만 최적해는 $4$와 $2$를 부딪히고 이제 남은 $2$끼리 부딪혀서 모두 없애는거죠. 언제나 가장 큰 것 2개를 부딪히는 것이 최적해인 것 같습니다. 어떻게 증명할 수 있을까요?

여러가지 상황이 있겠지만 우리가 근본적으로 피하고자 하는 상황은 다음과 같은 형태입니다.
$(1,\ 1,\ x)$ 여기에서 $1$끼리 먼저 부딪히는 바람에 $x$가 고스란히 남게 되는것이죠. 가장 큰 것 2개를 부딪히는 방법은 절대로 이와 같은 선택을 하지 않습니다. $x \ge 2$라고 가정해보겠습니다. 그러면 우리의 해법은 $x$와 $1$을 부딪히게 되고 이제 $x-1$과 $1$이 남습니다. $x$가 $1$이라면 뭐 어떻게 부딪혀도 다 똑같죠. 그러므로 가장 큰 것 2개를 부딪히는 방법은 절대로 손해를 보지 않습니다.

그래서 이 방법대로 구현하려고 보니... 입력의 크기가 문제입니다. 가장 큰 것 2개를 뽑아내는 방법은 우선 순위 큐로 쉽게 구현해서 $O(NlgN)$에 구현 할 수 있습니다. 그런데 구슬의 최대 개수는 $10^{14}$입니다. 직접 최적해를 실행 하는 것은 불가능합니다. 다른 방법이 있다는거겠죠 문제를 좀 더 관찰해봅시다.

최적해로 구슬을 부딪히면 언제나 단 한 종류의 구슬만 남거나 하나도 남지 않습니다. 두 종류 이상으로 남는다면 두 개를 부딪혀서 한 종류를 없앨 수 있기 때문이죠. 마지막으로 남는 구슬은 어떻게 한 종류만 남게 된 것일까요? 우리의 최적해는 절대로 손해를 보지 않는데 말이죠.

그 이유는 한 원소가 너무 커서 나머지를 다 부딪혀도 남는 경우입니다.

$max(S) \>> sum(S) - max(S)$

최적해를 선택하더라도 손해는 안 봤지만, 어차피 모두 없앨 수 없는 거죠. 이런 경우는 $max(S) - (sum(S) - max(S))$가 정답입니다.

위의 경우만 아니라면 손해는 절대 보지 않습니다. 총 합이 홀수인 경우만 빼고요. 그땐 당연히 $1$이 남겠죠.

$max(S) \le sum(S) - max(S)$

그런데 우리가 가장 큰 원소 두개씩 제거해나가는 과정에서 이 부등식이 깨지면 어떡하죠? 최적해를 따르면 이 부등식이 절대로 깨질일이 없음을 증명하겠습니다.

주어진 부등식을 이와 같이 바꾸겠습니다.
$max(S) \le \displaystyle\frac{sum(S)}{2}$ 그리고 이걸 깨기 위해 최대한 노력하겠습니다.
일반적으로 구슬을 부딪히는 과정에서 $max(S)$도 $1$씩 줄어들고 $sum(S)$도 $1$씩 줄어드는게 보통이지만, 무조건 그런 것은 아닙니다. $max(S)$가 여러 개 있다면 $max(S)$는 안줄어들 수도 있습니다. 이 점을 이용해서 최대한 부등식을 무너뜨리려고 노력해보겠습니다.

$S = [x,\ x,\ x,\ x,\ ...,\ x,\ x,\ x](N = |S|)$($N$은 홀수)
이러한 수열이 존재할 때, $N-1$(짝수)개를 서로 부딪혀서 없애면 $max(S)$는 변하지 않으면서 최대한 $sum(S)$를 줄일 수 있습니다. 이러한 과정을 부등식으로 나타내면 다음과 같습니다.
$x \le \displaystyle\frac{Nx-(N-1)}{2} \to x \le \displaystyle\frac{N(x-1)+1}{2}$
우변을 최대한 작게 해야 하므로 $x$에 $1$을 넣어 보겠습니다.
$1 \le \displaystyle\frac{1}{2}$
성립하지 않습니다. 원소들이 모두 $1$인 경우는 사실 바로 처리할 수 있으니 넘어갑시다.
$x$에 $2$를 넣어 보겠습니다.
$2 \le \displaystyle\frac{N+1}{2}$
$N \ge 3$일 때, 언제나 성립함을 알 수 있습니다.
그런데 사실 $N = 1,2$일 때는 너무나도 자명합니다. 그리고 우연인지 문제에서 의도한 것인지 모르겠지만 이 경우를 예외 처리하지 않고 아래와 같이 구현하더라도 맞습니다.

다음과 같이 해를 정리할 수 있습니다.
$max(S) - (sum(S) - max(S))\ (max(S) > sum(S) - max(S))$
$sum(S)\ \%\ 2\ (max(S) \le sum(S) - max(S))$

3. 구현

사실 짝수이면 다 없앨 수 있고 홀수이면 1개가 남는다는 직관이 맞기는 한데 예제 입력 2에서 바로 반례를 줘버리니 정말 문제를 손으로 계속 풀어보고 규칙을 찾는 것이 더 중요한 아이디어성 문제인 것 같습니다. 증명하기도 진짜 어렵네요

import sys
input = sys.stdin.readline
N = int(input())
S = [int(input()) for i in range(N)]
m = max(S)
s = sum(S)
print(m - (s - m) if m > s - m else s % 2)

1) 시간 복잡도

문제 설명을 위해서 $S$를 정렬한다고 했으나 사실 최대값만 필요한 것이므로 정렬 할 필요 없이 $O(N)$에 해결 할 수 있습니다.