[백준 2212 파이썬] - 센서

📌 문제

💯 정답

• 방법 1.

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
sensor = sorted(list(map(int, input().split())))	# 오름차순 정렬

if k >= n:
    print(0)
    sys.exit()

dist = []
for i in range(1, n):
    dist.append(sensor[i] - sensor[i-1])    # 센서들 거리의 차를 넣은 리스트

dist.sort(reverse=True)     # 거리의 차 내림차순 정렬
for _ in range(k-1):        # 집중국이 K일때 k-1개의 거리차 제거
    dist.pop(0)             # 내림차순했을 때 가장 큰 (가장 먼)

print(sum(dist))            # 나머지 거리의 합이 곧 수신 가능 영역 거리의 합 최솟값

• 방법 2.

import sys
input = sys.stdin.readline

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

dist = []
for i in range(1, n):
    dist.append(sensor[i] - sensor[i-1])    # 센서들 거리의 차를 넣은 리스트

dist.sort(reverse=True)         # 거리의 차 내림차순 정렬
print(sum(dist[k-1:]))          # k-1 번째부터 출력

📝 설명

• 방법 1.은 센서들의 거리의 차를 구해 내림차순으로 정렬한 뒤 가장 큰 값(가장 앞의 값)을 k-1개 pop 하고
  나머지 거리의 차들을 합해 구했다.

• 방법 2.는 센서들의 거리의 차를 구해 내림차순으로 정렬한 뒤 k-1번째 부터의 합을 구했다.

• 집중국이 K개 일때 K-1번 분할하면 K개의 구간으로 나뉘므로 가장 거리의 차가 큰 구간을 K-1개 찾아
  삭제하면(분할하면) 된다.

🙏 참고

👉 [알고리즘] 백준 221번 : 센서