[Python 문제풀이] 백준 2212번: 센서

문제

백준 2212번: 센서 (골드 5)

https://www.acmicpc.net/problem/2212

2212번: 센서

 

---

풀이과정

 

문제를 읽고 내가 생각해내지 못한 것?

집중국이 k개라는 것은, k개의 구간을 구하라는 것이다.

 

센서가 n개 이므로 우리는 위 그림처럼 센서 사이사이마다 연결고리를 체크하면

n-1개의 연결고리를 확인할 수 있다.

 

모든 센서가 연결되어 있으므로 현재 구간의 개수는 1개이다.

 

만약 연결고리를 i개 제거했다고 했을때, 구간은 i+1개가 되는데,

집중국이 k개 이므로 i+1은 k가 되어야 한다.

i + 1 = k

i = k - 1

 

이므로, 우리는 n-1개의 연결고리 중 k-1개를 제거해야 한다.

 

 

여기서 문제의 조건을 다시 보면, 우리는 k개의 구간이 가장 최소인 프로그램을 작성해야 한다.

그러므로, 각각의 연결고리 사이의 구간을 정렬했을때, 앞에서 n-k개의 구간을 더해주면 되는 것이다.

(연결고리 n-1개 중에서 k-1개를 제거해야 하므로 --> n-k개가 됨.)

 

---

제출한 코드

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())
sensors = list(map(int, input().split()))
sensors.sort()	# 센서 저장 배열

array = []	# 구간 저장 배열
for i in range(n-1):
    array.append(sensors[i+1] - sensors[i])
array.sort()

print(sum(array[:n-k]))