백준 2212 센서 Python 3

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

2212번: 센서

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2212.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
input = sys.stdin.readline
N = int(input())
K = int(input())
if K >= N: print(0)
else:
    sensors = sorted(list(map(int, input().split())))
    dis = list()
    for i in range(N-1):
        dis.append(sensors[i+1]-sensors[i])
    dis.sort(reverse=True)
    print(sum(dis[K-1:]))

---

풀이 과정

문제를 읽고 예제를 보았는데 이해가 되지 않아서,, 블로그들을 보며 참고했다.

센서 N개가 적어도 1기의 집중국과 통신할 수 있도록 집중국을 K개 설치해야 한다.

이때, K개의 집중국의 수신 가능 영역의 길이의 합이 최소가 되어야 한다.

 

말로서 이해하기 어려우니 예제 1번, 2번을 풀어보자.

빨간색으로 표시된 부분이 설치된 집중국의 수신 가능 영역이다.

 

즉, 센서의 좌표들을 오름차순으로 정렬하고 센서와 센서 사이의 거리들을 구한 뒤, 거리가 큰 순서대로 K-1개를 빼고 남은 거리의 합을 구해주면 답이 나온다.

 

주의해야할 점은 집중국의 개수 K가 센서의 개수 N보다 크거나 같은 경우에는 그냥 각 센서마다 수신 가능 영역이 0인 집중국을 하나씩 설치하면 되기 때문에 정답은 0이 된다는 점이다.

import sys
input = sys.stdin.readline
N = int(input())
K = int(input())

#집중국의 개수가 센서 개수 이상인 경우,
if K >= N: print(0)

#집중국의 개수가 센서 개수보다 적은 경우,
else:
	#센서 좌표들을 오름차순 정렬
    sensors = sorted(list(map(int, input().split())))
    
    #센서 사이의 거리들을 구하여 dis 리스트에 담는다
    dis = list()
    for i in range(N-1):
        dis.append(sensors[i+1]-sensors[i])
        
    #센서 사이의 거리들을 내림차순 정렬
    dis.sort(reverse=True)
    
    #가장 거리가 먼 K-1개를 제외한 나머지 거리의 합을 출력한다
    print(sum(dis[K-1:]))

#시간복잡도 = O(nlogn), 공간복잡도 = O(n)