[Gold V]
https://www.acmicpc.net/problem/2212
2212번: 센서
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있
www.acmicpc.net
풀이
간단한 Greedy 문제.
처음에는 집중국의 수신 가능 영역이, 각 집중국이 수신할 수 있는 "범위" 인 줄 알았으나,
(좌표 3에서 수신범위가 2라면 1~5를 커버한다는 생각.)
그냥 진짜로 literally 집중국이 수신하는 영역을 나타내는 거였다. 꼭 주위 N만큼의 범위를 수신하는 것이 아니라, 앞으로 2칸, 뒤로 3칸 이렇게도 가능한 것.
그렇다면 문제는 굉장히 쉬워진다.
예제 입력 1을 보자.
6
2
1 6 9 3 6 7
센서를 좌표별로 정렬하면,[1, 3, 6, 6, 7, 9] 이다.
집중국을 최대 2개 설치할 수 있다는 것은,
=> 센서 사이의 공백을 최대 한 칸 무시할 수 있다는 것과 같다.
이것을 일반화하면, 집중국을 K개 설치할 수 있을 때, 센서 사이의 공백을 최대 K-1개 무시할 수 있는 것이다.
예제 입력 1에서, 센서 사이의 공백은 각각 [2, 3, 0, 1, 2] 이고,
이를 정렬하여, 제일 큰 값 하나를 지우고, 모든 값을 더하면 답이 된다.
일반화하면, 센서 사이의 공백을 모두 계산하고, 그것을 정렬한 후, 제일 큰 값부터 K-1개를 제외하고 모두 합하면 된다.
AC.
N = int(input())
K = int(input())
sensor = list(map(int, input().split()))
sensor = sorted(sensor)
gap = []
for i in range(len(sensor)-1):
gap.append(sensor[i+1] - sensor[i])
gap = sorted(gap)
if K != 1:
print(sum(gap[:-(K-1)]))
else:
print(sum(gap))