[BOJ] 백준 2212번 - 센서 (Python)

문제

문제 바로가기

N개의 센서가 있고, 리스트의 값들은 원점으로부터 각각의 센서가 얼마나 거리에 있는 지 나타낸다. K개의 집중국은 K개의 가장 밀집된 클러스터에 배정되어 수신 가능 영역의 길이의 합이 최소가 되도록 해야한다.

문제 해결

집중국을 어디에 위치하는 것은 중요한 게 아니고, 각각의 집중국의 수신 가능 영역의 길이의 합만 구하면 되기 때문에 사실상 가장 잘 뭉쳐있는 영역 K개만 구하고, 각각의 영역에서 센서들의 거리의 차들을 더하면 되는 문제이다.

예를 들어 sensor의 리스트가[1, 3, 6, 6, 7, 9]일 때 K가 2일 경우를 보자.

이때 각각 거리의 차는 [2, 3, 0, 1, 2]이다.

그럼 가장 먼 거리인 3을 기준으로 2개의 클러스터로 나눈 뒤 각 클러스터에서의 센서 간 거리를 합하여 풀면 되는 것이다.

그럼 여기서 굳이 2개의 클러스터로 나누어야 할까?

K가 2이면 가장 큰 센서 간 거리 1개를 뺀 뒤 모두를 더하고, K가 3이면 가장 큰 센서간 거리 2개를 뺀 뒤 모두를 더하면 되는 것이다.

즉 위의 예시의 [2, 3, 0, 1, 2]에서는 3을 뺀 모두를 더하면 된다.

그럼 코드로 매우 간단하게 작성이 가능해진다.

로직은 다음과 같다.

1. N개의 센서의 위치를 sort한다.
2. 센서끼리의 거리의 차를 구한다.
3. 거리의 차를 내림차순으로 sort한다.
4. 내림차순 리스트에서 [K-1:]를 모두 더한다.

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

sensor.sort()

distance = list()
for i in range(len(sensor) - 1):
  distance.append(sensor[i+1] - sensor[i])

distance.sort(reverse=True)

for area in distance[k-1:]:
  total_area += area

print(total_area)