반응형
대회 당시에 풀고싶었는데
정렬을 해야할거 같기는 한데 매번 정렬하면 시간초과가 나오지 않을까?
하는 생각으로 풀다 말았었는데 야매로 풀었다.
1440 을 넘어가면 -1을 출력하게 해줬다
지금 생각해보면 처음 입력받은 li 를 내림차순으로 정렬해준 뒤 확인했어야 하지 않나 싶은데
어찌됐든 통과는 했다
정렬은 sort 가 아니라 우선순위 큐를 사용했다
작은 숫자부터 먼저 빠져나오기 때문에 억지로 음수로 전환하는 작업을 해줬다.
arr 에 요소가 하나 이상 있다면 두 집에서 눈을 치우는게 이득
하나밖에 없다면 그 집에서밖에 눈을 치울 수 없기 때문에 조건문으로
인덱스 에러가 나지않게 처리해 주었다
from heapq import heappop, heappush
n = int(input())
li = list(map(int, input().split()))
arr = []
if li[0] > 1440:
print(-1)
exit()
for i in li:
heappush(arr, -i)
# print(arr)
cnt = 0
while arr:
if len(arr) >= 2:
a = heappop(arr)
b = heappop(arr)
a += 1
b += 1
if a != 0:
heappush(arr, a)
if b != 0:
heappush(arr, b)
else:
a = heappop(arr)
a += 1
if a != 0:
heappush(arr, a)
cnt += 1
if cnt > 1440:
cnt = -1
print(cnt)
https://www.acmicpc.net/problem/26215
반응형
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 2636 치즈 (파이썬) (0) | 2022.11.10 |
---|---|
백준 1197 최소 스패닝 트리 (파이썬) (0) | 2022.10.28 |
백준 5014 스타트 링크 (파이썬) (0) | 2022.10.13 |
백준 8979 올림픽 (파이썬) (0) | 2022.09.26 |
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |