백준 19590번 파이썬 문제풀이(비드맨)

https://www.acmicpc.net/problem/19590

19590번: 비드맨

---

딱 코드포스 같은곳에서 좋아할 문제이다.. N이 아주 크고 그리디....

 

아이디어 생각하기 정말쉽지 않은 문제이다.

단 생각하고나면 간단하다.

 

가장 큰 값과 총 합을 찾는다.  만약 (총합 - 가장 많은 구슬의 개수) - 가장 많은 구슬의 개수 가 음수라면 즉, 가장 많은 구슬의 개수를 제외한 나머지 구슬들의 합이 더 적다면 그냥 가장 많은 구슬의 개수 - 나머지 구슬 개수의 합이 답이다. 

 

그러나 반대로 위의 값이 양수라면 조금 더 생각을 해봐야한다.

 

나머지 구슬들의 합에서 자기들 끼리 치고 없애서 가장 많은 구슬의 개수와 맞춰주는 것이다. 그런데 총 합이 짝수이면 딱 맞게 맞출수 있으나 홀수이면 1개 차이나게 만들 수 있다.

 

import sys

input = sys.stdin.readline
N = int(input())
sum_ = 0
max_ = 0
for _ in range(N):
    num = int(input())
    sum_ += num
    if num > max_:
        max_ = num

if sum_ - max_ <= max_:
    print(max_ - (sum_ - max_))
else:
    if sum_ % 2:
        print(1)
    else:
        print(0)