[파이썬/python] 백준 - 19590 비드맨

문제

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

---

문제 설명

1. 구슬의 종류 N과 $x_1,x_2,x_3....x_N$총 N개의 i번째 종류의 구슬의 개수 $x_i$가 주어진다.
2. 구슬 두 개를 부딪히면 서로 깨져 없어진다.
3. 현재 가지고 있는 구슬의 개수를 최소로 했을 때 남은 구슬의 개수를 출력한다.

---

풀이

처음에는 단순하게 힙을 사용한 시뮬레이션 방식으로 접근했다.

가장 큰 값에서 작은 값을 순차적으로 빼면 정답이 나오지 않을까 생각하며 코드를 작성했다.

하지만 결과는 틀렸고, 반례가 존재했다.

 

예를 들어 구슬의 개수가 [6, 4, 4]라고 해보자.

 

내가 처음 생각했던 방식대로라면 6에서 4를 빼서 [4, 2]가 되고, 다시 4에서 2를 빼면 결과는 2가 된다. 따라서 정답이 2라고 생각할 수 있다.

 

하지만 실제로는 다른 방식으로 진행할 수 있다. 먼저 4와 4를 한 번 부딪히면 [6, 3, 3]이 된다. 이후 6에서 두 개의 3을 제거하면 모든 구슬을 제거할 수 있으므로 정답은 0이 된다. 따라서 단순히 가장 큰 값에서 작은 값을 빼는 방식은 올바른 풀이가 아니다.

 

문제를 다시 생각해 보면 구슬은 항상 서로 다른 종류 두 개를 부딪혀 제거한다. 즉 한 번의 연산이 일어날 때마다 구슬의 총 개수는 정확히 2개씩 감소한다.

 

예시 [6,4,4]를 다시 살펴보자. 각 구슬을 각각 A, B, C라고 하겠다.

 

가장 많은 구슬인 A를 기준으로 다음과 같이 제거할 수 있다.

 

A-B → A-C → A-B → A-C → A-B → A-C

 

이 과정을 진행하면 상태는 [0,1,1]이 된다. 이후 B와 C를 한 번 더 부딪히면 모든 구슬이 사라지게 되어 결과는 0이 된다.

 

비슷한 예시로 [6,4,3]을 생각해 보자. 같은 방식으로 진행하면

 

A-B → A-C → A-B → A-C → A-B → A-C

 

의 순서로 제거할 수 있고 결과는 [0,1,0]이 된다. 따라서 최종적으로 1개의 구슬이 남는다.

 

이처럼 가장 많은 구슬을 기준으로 나머지 구슬들과 계속 부딪히다 보면 마지막에는 0개 또는 1개의 구슬이 남게 된다. 즉 전체 구슬의 홀짝성에 따라 결과가 결정된다.

 

이를 정리하면 다음과 같다.

 

Total은 전체 구슬의 개수이고, M은 가장 많은 구슬의 개수라고 하자.

 

만약 가장 많은 구슬의 개수 M이 나머지 구슬의 개수인 Total - M보다 작거나 같다면, 모든 구슬을 서로 다른 종류끼리 계속 부딪힐 수 있다. 이 경우 마지막에는 전체 구슬 수의 홀짝성만 남게 되므로 정답은 Total % 2가 된다.

 

하지만 [6,1,1]과 같은 경우를 보면 상황이 달라진다. A-B, A-C를 수행하면 [4,0,0]이 된다. 이 경우 더 이상 다른 종류의 구슬이 없기 때문에 남은 A끼리는 제거할 수 없다. 따라서 4개의 구슬이 그대로 남게 된다.

 

이러한 상황은 가장 많은 구슬의 개수 M이 나머지 구슬의 개수 Total - M보다 많은 경우에 발생한다. 이 경우에는 모든 구슬을 서로 짝지어 제거할 수 없기 때문에 M - (Total - M)개의 구슬이 반드시 남게 된다.

 

위에서 도출한 결과를 통해 아래와 같이 조건을 나눌 수 있다.

 

1. M < Total - M (가장 큰 구슬의 개수가 나머지 구슬의 개수보다 많을 때)
=> (Total-M) % 2

2. M > Total - M (가장 큰 구슬의 개수가 나머지 구슬의 개수보다 적을 때)
=> M - (Total - M)

 

이를 그대로 구현하면 문제를 해결할 수 있다.

 

---

코드

import sys
input = sys.stdin.readline

N = int(input())

arr = []
total = 0
mx = 0

for _ in range(N):
    x = int(input())
    total += x
    mx = max(mx, x)

if mx > total - mx:
    print(mx - (total - mx))
else:
    print(total % 2)

---

시간복잡도

• 최댓값과, Total을 구할 때 N번 반복하므로 $O(N)$의 시간복잡도를 가진다.