[파이썬/python] 백준 - 15553 난로

문제

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

---

문제 설명

1. 구사과의 방에는 난로가 하나 있다. 난로는 친구가 방에 왔을 때 항상 켜야한다.
2. N명의 친구가 집에 방문할 것이다.
   1. i번째 친구는 시간 $T_i$에 도착하고 $T_{i+1}$에 나간다.
   2. 방은 좁기 때문에 한 번에 한 명만 방문할 수 있다.
3. 난로는 아무때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 하는데 총 K개의 성냥을 가지고 있다.
   1. 처음에는 난로가 꺼져있다.
4. 이 때 난로가 켜져 있는 시간을 최소로 했을 때 시간을 구한다.

---

풀이

문제를 요약하자면, K개의 성냥을 사용해서 난로를 켜고 끄면서 전체 난로 가동 시간을 최소로 만드는 것이 목표다.

 

그래서 처음에는 자연스럽게 “난로를 최대한 덜 켜야겠다”는 생각이 들었고, 그리디로 접근해야겠다고 판단했다.

 

문제를 풀기 전에 한 가지 확실하게 알 수 있는 점이 있다.

 

첫 번째 친구가 오면 난로는 무조건 켜야 한다. 이말은 즉 시작할 때 성냥 1개는 반드시 사용하게 된다는 것이다.

 

그래서 처음 상태는 아래와 같이 시작하게 된다.

• 난로 켜진 시간: 1
• 남은 성냥: K - 1

이제 하나의 상황을 예를 들어보자.

3 2
1
3
6

위의 상황에 대해서 결과를 구해보면 다음과 같다.

 

 

1초 : 성냥 1개 사용 (난로 ON)
2초 : 난로 ON
3초 : 난로 ON
4~5초 : 난로 OFF
6초 : 성냥 1개 사용 (난로 ON)
7초 : 난로 OFF

 

총 0-3(3초) + 6-7(1초) = 4초의 시간이 걸렸음을 알 수 있다.

 

여기서 중요한 포인트는
두 번째 친구가 나간 이후, 세 번째 친구가 오기 전까지는 난로를 꺼두었다가 다시 켰다는 점이다.

 

아직까지는 제대로 이해가 되지 않을 수 있다.

 

각 친구 사이의 간격이 존재한다.

위 예시에서는

• 1번 -> 2번 : 2초
• 2번 -> 3번 : 3초

이렇게 간격이 생긴다.

 

이때 우리는 성냥을 사용해서 난로를 다시 켤 수 있기 때문에,
간격이 큰 구간에서는 굳이 계속 켜둘 필요가 없다.

 

즉 간격이 큰 곳에서 난로를 꺼두고, 다시 켜는 데 성냥을 사용하는 것이 더 이득이라는 말이다.

 

한마디로 가장 큰 간격이 존재하는 시간에 성냥을 사용하는 것이 최적이라는 것을 알 수 있다.

 

좀 더 복잡한 예시를 통해 정답을 구해보자.

10 5
1
2
5
6
8
11
13
15
16
20

각 친구 사이의 간격을 모두 구하면 [1, 3, 1, 2, 3, 2, 2, 1, 4]이다.

 

총 4개의 양초를 사용할 수 있으므로 가장 큰 간격을 가진 시간들에 양초를 사용하게 되면 [1, 3, 1, 2, 3, 2, 2, 1, 4] 이렇게 사용하게 될 것이다.

 

이 때 양초를 사용한다는 것은 그 전까지 난로를 꺼 두었다가 다시 켜는 과정이기 때문에 양초를 사용한 간격은 총 1초의 시간만 소요하게 된다.

 

따라서 빨간색으로 칠한 부분은 전부 1초의 시간이 소요되게 되고 나머지는 그대로 시간이 소요되게 된다.

즉 1 + 1 + 1 + 1 + 1 + 2 + 2 + 1 + 1 = 12초라는 결과를 도출할 수 있다.

 

우리는 배열 안에서 K-1개의 가장 큰 값을 구해야 한다.

 

해당 배열을 정렬하고 앞에서부터 K-1개를 1로 바꾸는 방법도 있지만, 나는 처음 배열을 만들때 heap 구조를 사용해서 최대힙을 통해 정답을 구했다.

 

큰 값을 꺼낼 때 마다 K-1을 진행하고 1초를 더했다. K가 0이되면 기존 시간을 그대로 더해준 후 최종 정답을 출력했다.

 

그리디 문제는 이렇게 어떤 선택이 항상 최적인지만 잘 판단(이게 제일 어렵지만)하면 구현 자체는 크게 어렵지 않은 것 같다.

---

코드

import sys
import heapq
input = sys.stdin.readline

N, K = map(int,input().split())
arr = [int(input()) for _ in range(N)]

arr.sort()

hq = []
sec = 1
for i in range(1,N):
    heapq.heappush(hq,-(arr[i]-arr[i-1]))

K -= 1
while hq:
    s = -heapq.heappop(hq)
    if K > 0:
        sec += 1
        K -= 1
    else:
        sec += s

print(sec)

---

시간복잡도

• 힙에서 데이터를 꺼낼 때 $logN$만큼이 걸리고 총 N개의 데이터를 꺼낸다.
• 즉 $O(NlogN) = O(5000*log{5000}) = O(6*10^4)$의 시간복잡도를 가진다.