[백준 2212번] 센서

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

import sys
import heapq

input = sys.stdin.readline

# 고속도로 위에 N개의 센서를 설치
# 고속도로 위에 최대 K개의 집중국을 세울 수 있다

# 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다
# 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다

# N개의 센서는 적어도 하나의 집중국과는 통신이 가능해야함
# 각 집중국의 '수신 가능 영역의 길이의 합'을 최소화

# 고속도로는 평면상의 직선이라고 가정
# 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다
# 따라서, 각 센서의 좌표는 정수 하나로 표현

# 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

# 출력 : 각 집중국의 수신 가능영역의 거리의 합의 최솟값

N = int(input())
K = int(input())

sensors = sorted(list(set(map(int,input().split()))))
diffs = []

for i in range(len(sensors)-1):
    heapq.heappush(diffs,-abs(sensors[i+1]-sensors[i]))

for _ in range(K-1):
    if diffs:
        heapq.heappop(diffs)

diffs = [-x for x in diffs]

print(sum(diffs))

 

이번 문제는 직선 상에 N개의 센서를 설치하였고, 이를 관리하기 위한 K개의 집중국을 세운다고 했을 때 집중국의 센서 수신 가능 영역의 최솟값을 구하는 문제이다.

 

문제를 처음 읽었을 때는 무슨 말인지 이해가 잘 가지 않을 수 있는데, 쉽게 이야기하자면 정확히 K개의 집중국을 설치하되 각 집중국의 센서 범위를 최소화하면서 모든 센서를 탐지할 수 있도록 하는 문제이다.

 

해당 문제를 풀기 위해서 모든 센서 값들을 오름차순으로 정렬하고 각 센서 사이간의 간격을 저장해주었다. 그 후 간격들 중 가장 큰 최댓값을 K-1번 제거해주면 최소한의 거리로 모든 센서를 탐지하는 K개의 집중국이 남게 된다.(Greedy 알고리즘)

 

추가적으로 최댓값을 효율적으로 찾아서 제거하기 위해 heap 자료구조를 사용하였다.

 

그리디 알고리즘을 복습해볼 수 있었던 문제였다 :)