[백준] 26215 눈 치우기

문제

지난 밤 겨울 숲에는 눈이 많이 내렸다. 당신은 숲의 주민들을 위해 눈이 오지 않는 동안 모든 집 앞의 눈을 치우고자 한다.

당신은 1분에 한 번씩 두 집을 선택해서 두 집 앞의 눈을 각각 1만큼 치우거나, 한 집을 선택해서 그 집 앞의 눈을 1만큼 치울 수 있다.

모든 집 앞의 눈을 전부 치울 때까지 걸리는 최소 시간은 얼마일까?

입력

첫 줄에 집의 수를 의미하는 정수 $N$ ( $1 \leq N \leq 100$ )이 주어진다.

다음 줄에는 각각의 집 앞에 쌓여 있는 눈의 양을 나타내는 정수 $a_{i}$ ( $1 \leq a_{i} \leq 2000$ )이 주어진다.

출력

모든 집 앞의 눈을 치우는 데 최소 몇 분이 걸리는지를 출력한다. 24시간(1440분)이 넘게 걸릴 경우 -1을 출력한다

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int, input().split()))

cnt = 0

if n == 1:
    cnt += list1[0]
else:
    while sum(list1) != 0:
        list1.sort(reverse=True)
        if list1[0] != 0 and list1[1] != 0:
            cnt += list1[1]
            list1[0] -= list1[1]
            list1[1] = 0
        else:
            cnt += list1[0]
            list1[0] = 0
    
if cnt > 1440:
    print(-1)
else:
    print(cnt)

코멘트

모든 눈을 최단 시간에 치우는 방법은 가장 눈이 많이 쌓인 두 집을 골라 2번째로 눈이 많이 쌓인 집 만큼의 눈을 치운 후 (1번째로 눈이 많이 쌓인 집만큼의 눈을 치우면 음수가 되어버리므로...) 눈이 쌓인 집이 한 집만 남았을 때에는 그 집만 치우고 마무리하는 것이다.

heapq로 구현하면 더 빠르고 효율적으로 될런지...?

[백준] 26215 눈 치우기

문제

입력

출력

내 풀이

코멘트

References