[알고리즘/그리디] 2212번 : 센서 - python

링크 : https://www.acmicpc.net/problem/2212

2212번: 센서

 

---

• 문제
• 소요시간: 12분 7초(구현 9분 10초)

---

• 설계하기(접근방법) 

1. 입력받기

센서

집중국

센서의 좌표를 입력받는다

 

2. 구현하기

이전의 행복 유치원과 매우 유사하 문제이니 구현 부분은 생략하겠다

다만 집중국의 개수가 센서의 개수보다 많은 경우

집중국의 개수가 센서의 개수와 동일한 사례와 같으므로

조건문으로 처리해준다

 

3. 출력하기

최소 범위의 합을 출력한다

 

 

---

• 코드(출력)

import heapq

sensor = int(input())
center = int(input())
sensor_list = list(map(int,input().split()))

sensor_list.sort()

if sensor < center:
    center = sensor


total = sensor_list[-1] - sensor_list[0]
h = []

for i in range(sensor - 1):
    difference = sensor_list[i + 1] - sensor_list[i]
    heapq.heappush(h, -difference)

except_cnt = 0

for i in range(center - 1):
    except_cnt += heapq.heappop(h) * (-1)

print(total - except_cnt)

---

• 얻어갈 부분

1. 이전 문제와 유사한 부분이 많아 쉽게 구현했다. 하지만 집중국의 개수가 센서보다 많은 경우 list out of range를 출력하게 되므로, 이 경우 두 수를 동일하게 만드는 조건문을 달아서 해결했다