[백준(BOJ)] 2212번 센서 - 파이썬/python

문제

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

2212번: 센서

고속도로에 N개의 센서가 있고, 최대 K개의 집중국을 설치할 수 있는데, 각 집중국은 수신 가능한 영역을 조절할 수 있다. 센서와 적어도 한 집중국은 통신 가능해야 하며, 집중국의 유지비로 인해 각 집중국의 수신 가능 영역의 길이 합을 최소화해야 한다. K개의 집중국의 수신 가능 영역의 길이 합의 최솟값을 구하는 문제다.

 

예시

Example 1:

Input: 6
       2
       1 6 9 3 6 7
Output: 5

 

Example 2:

Input: 10
       5
       20 3 14 6 7 8 18 10 12 15
Output: 7

풀이

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
sensor = list(map(int, input().split()))
sensor.sort()

# 센서 간 거리 추가 및 내림차순으로 정렬
distance = []
for i in range(n - 1):
    distance.append(sensor[i + 1] - sensor[i])
distance.sort(reverse=True)

# 센서 거리 상위 K - 1개를 제외한 거리 합
print(sum(distance[k - 1:]))

- 문제에 대한 이해를 하는 데 오래 걸렸는데 그림을 그려보면 좀 더 이해하기 쉬워진다.

- n개의 센서를 k개로 나눠야 하기 때문에 k-1 개의 구분선이 필요하다.

- 각 센서의 좌표를 오름차순으로 정렬하고, 센서 간 거리를 계산하여 내림차순으로 정렬한다.

- 센서 간 거리의 상위 k-1개를 제외한 나머지 거리의 합을 계산하여 출력한다.