[Python 알고리즘] 백준 2212번 : 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

 

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

 

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

 

예제 입력

# Case 1
6
2
1 6 9 3 6 7

# Case 2
10
5
20 3 14 6 7 8 18 10 12 15

 

예제 출력

# Case 1
5

# Case 2
7

 

내가 제출한 풀이

import sys

sensor_cnt = int(sys.stdin.readline().strip())
building_cnt = int(sys.stdin.readline().strip())
sensor_distances = list(map(int, sys.stdin.readline().strip().split()))

sensor_distances.sort()

diffs = [
    sensor_distances[i + 1] - sensor_distances[i] 
    for i in range(0, len(sensor_distances) - 1)
]
diffs.sort()

result = sum(diffs[0:len(diffs) - (building_cnt - 1)])
print(result)

 

문제 해설

이번 문제에서는 문제의 내용을 이해하느라 좀 어려웠었다. 그러니 문제에 대한 내용부터 이해하고 가보자. Case 1의 기준으로 설명된다.

 

"각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다." 라는 뜻은 다음과 같다.

• 센서 개수 : 6개
• 기지국 개수 : 2개
• 최소의 합 : 5

"평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다."를 통해 센서들을 한 기점을 중심으로 센서들이 좌표마다 배치되어 있다고 한다. 여기서 원점은 맨 왼쪽 0 (따로 표시는 하지 않음)부터 시작한다고 보면 된다. 집중국은 총 2개이니 센서들을 2개의 묶음으로 만들 수 있고 그 묶음의 합이 최솟값이면 되는 것이다. 그리고 6은 2번 중복되었기 때문에 6을 1개로 칠 수 있다.

그러면 이제 코드를 보자.

 

위와 같은 형태를 적용한다면, 센서들의 좌표를 오름차순 정렬하여 각 좌표마다의 차이를 구해 그 중 최소의 합을 찾으면 되는 것이다. 여기서 최소의 합을 구하는 방법은 가장 차이가 많이 나는 좌표들은 1개의 기지국으로 묶어 합을 0으로 만드는 것이다. 즉, 기지국 1개를 가져가는 좌표들의 개수는 기지국 - 1개이다. 나머지 1개의 기지국은 하나로 묶어 최소의 합을 구하면 되는 것이다.

어떻게 보면 저번에 포스팅한 행복한 유치원과 같은 케이스라고 볼 수 있다.

sensor_distances.sort()

diffs = [
    sensor_distances[i + 1] - sensor_distances[i] 
    for i in range(0, len(sensor_distances) - 1)
]
diffs.sort()

센서들의 좌표를 오름차순 정렬하여, 각 좌표들의 차이를 오름차순을 정렬한다. 이 때 주의할점은 i + 1 값을 i의 값으로 빼야 한다는 것이다. 왜냐하면 오름차순 정렬로 인해 i + 1의 값이 무조건 i의 값보다 높기 때문이다.

 

result = sum(diffs[0:len(diffs) - (building_cnt - 1)])
print(result)

 

좌표들의 차이 값에서 기지국 개수 - 1개만 묶어 합을 구하면 된다. 즉, 기지국 하나로 1개의 좌표로만 구성되어 있는 것은 센서의 차이 값이 큰 애들만 있고, 그 외 차이 값이 적은 애들은 1개의 기지국으로만 이루어져있는 것이다.