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

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

19590번: 비드맨

문제 해석

 

n개의 종류의 구슬의 갯수가 주어진다. 종류가 서로 다른 구슬 2종류를 부딪혀 구슬을 깨뜨릴 수 있다. 구슬을 서로 부딪혀 최소로 남개되는 구슬의 수를 구하여라.

---

코드

 

input = __import__('sys').stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
_max = max(arr)
_sum = sum(arr)

# n == 1: 부딪힐 구슬이 없어 그냥 답
if n == 1: print(arr[0])
else:
    # 가장 많은 구슬이 다른 종류의 구슬들보다 큰 경우 다른 종류의 구슬들이 모두 가장 큰 구슬에 부딪혀 없애고 남은 값이 답
    if _max >= _sum - _max: print(_max - (_sum - _max))
    # 아닌 경우 구슬의 총 합이 홀수면 1 아니면 0
    else:
        if _sum % 2: print(1)
        else: print(0)

---

문제 풀이

 

1. heap을 사용하여 최대 우선순위 큐로 넣어 가장 큰 구슬 2개를 뽑아 줄여나가면 된다고 생각했다.

3
2
2
2

하지만 다음과 같은 입력이 주어졌을 때 출력이 2가 나오게 된다. 이 경우 각 종류의 구슬이 하나씩 부딪혀 답이 0으로 출력되어야 한다.

 

 

2. 따라서 가장 우선순위 큐에서 2개의 구슬을 뽑아 서로 -1 을 해주는 방법을 생각해 보았다. 역시나 시간 초과가 발생하였다.

 

 

3. 구슬의 갯수를 크기로 생각하고, 가장 크기가 큰 구슬이 나머지 구슬의 총합보다 크다면 나머지 구슬이 가장 큰 구슬에 부딪혀야 최소가 된다. 

3
150
50
10

다음과 같은 입력이 주어졌다면 최대값 150 >= 60 이므로 답은 90이 된다.

 

해당 외의 경우에는 결국 구슬이 서로 부딪혀 구슬의 총합이 짝수일때는 0, 홀수일때는 1이 출력되게 된다.

 

다음과 같은 알고리즘으로 맞았다!