문제
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
내 코드
import sys
sys.stdin = open("input.txt", "rt")
# n개의 센서, k개의 집중국
# n개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 함.
# 각 집중국의 수신 가능 영역의 길이의 합을 최소화.
# 그리디적으로 딱 센서가 위치한 곳에 일단 집중국을 놔야 한다.
n = int(input())
k = int(input())
data = list(map(int, input().split()))
if k >= n:
print(0) # 모두 커버 가능하므로
else:
data.sort()
sense_length = [0] * n
for i in range(1,n):
sense_length[i] = data[i] - data[i-1]
sense_length.sort(reverse = True)
# print(sense_length)
print(sum(sense_length[k-1:]))
코멘트
문제를 천천히 읽어보고 테케가 어떻게 하면 나오게 되는지 이해가 안된다면 테케를 통해 문제를 해결해보자.
예시 데이터를 기준으로 정렬만 해서 본다면
1 3 6 6 7 9 이다.
k개의 집중국으로 모든 센서를 커버할 수 있도록 하는 각 집중국 범위의 합을 구해야 한다.
가장 큰 예외처리 : if k>=n이라면 무조건 0이므로 끝
1. 센서개수 n, 집중국의 개수k 센서의 위치를 입력 받는다.
2. 센서의 위치를 오름차순 정렬한다.
3. 정렬된 센서의 위치에서 인접한 센서 간의 거리를 계산하여 구한다.
4. 내림차순 진행
코드의 핵심은 가장 큰 거리부터 k-1개를 제외한 나머지 거리의 합이 최소가 되는 경우를 찾는 것이었다.
왜냐하면 가장 큰 거리에서 집중국을 설치하면 그 거리를 줄일 수 있기 때문 (그리디적 마인드)
예를 들어 , [1,3,6,7,9]이고 k=3인 경우
센서 정렬 시 1,3,6,7,9
인접한 센서 간의 거리 [2,3,1,2]
내림차순 정렬 [3,2,2,1]
k-1 =2개의 거리를 제외하면 [2,1] 남는다.
이 경우 최소 집중국 개수 1+2 = 3
핵심 아이디어인 k개의 집중국을 세우게 되면 집중국과 집중국 사이 빈 공간 k-1개가
생기게 된다. 이 k-1개의 빈 공간을 가장 크게 하면 도니다.
백준 링크텍스트[행복 유치원]도 함께 풀어보자.
