1. 오늘의 문제
오늘은 또리디 알고리즘이다.
그런데 문제는 아무리 봐도 어떻게 문제를 풀어나가야 할지 감이 오지 않았다.
내가 알던 그리디 알고리즘 맞니...?
결국 티스토리 형님들의 힘을 빌렸다.
문제
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
2. 원리
핵심은 집중국에 의해 채워지는 범위를 보는 것이 아니었다.
집중국을 설치하면 (집중국의 개수 - 1) 만큼의 빈 공간이 남게 되니, 이 빈 공간을 최대화 시키는 방향으로 진행하는 것.
그리고 나머지 공간에 집중국을 세우면 집중국의 수신 거리가 최소가 되도록 할 수 있다.
3. 코드
from sys import stdin
put = stdin.readline
numOfSensor = int(put())
center = int(put())
sensorPosi = list(map(int, put().split()))
sensorPosi.sort()
gaps = []
for i in range(len(sensorPosi)):
if i + 1 >= len(sensorPosi):
break
gap = sensorPosi[i+1] - sensorPosi[i]
gaps.append(gap)
gaps.sort()
gaps.reverse()
gaps = gaps[center-1:]
total = 0
for gap in gaps:
total += gap
print(total)
4. 느낀점
뒤통수를 세게 맞은 것 같다.
그 동안 그리디 알고리즘으로 문제를 해결할 때는 해결해야 하는 값 자체에 집중했다.
이번 문제는 그 값보다는, 값 자체를 제외한 나머지에서 영감을 얻어야 했다.
아직 갈길은 멀다.
