[BOJ] 2212 : 센서 [그리디](Python)

문제 링크

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

2212번: 센서

소스 코드

import sys

n = int(input())
k = int(input())

centers = sorted(list(map(int,sys.stdin.readline().strip().split()))) # 센터 위치 오름차순
dists = sorted([centers[i]-centers[i-1] for i in range(1,n)],reverse=True) # 거리 내림차순
print(sum(dists[k-1:]))

 

해설

• 그리디

시간복잡도

centers라는 list를 오름차순으로 정렬하는 것은 내장 함수를 사용하기 때문에 O(NlogN) 입니다.

또한 dist를 구할 때 같은 길이(정확히는 n-1)에 대해 정렬을 수행하는 것도 O(NlogN) 입니다.

 

따라서 총 시간복잡도는 O(NlogN) 이 됩니다.

풀이

주어지는 입력 리스트를 정렬하게 되면 원점에서 얼마나 멀리 떨어져 있는지를 순서대로 나타낼 수 있습니다.

이제 각 기지국 사이의 거리를 구한 리스트 dists를 만들어줍니다.

그리고 이를 내림차순으로 정렬합니다.

 

각 이 거리의 값이 가장 큰 것부터 k-1 개를 덜어내고 합을 구하면 정답이 됩니다.

 

k개의 집중국을 설치하게 되면 k개 구역으로 나눠지게 되고 각 구역의 최대-최소의 값이 각 집중국이 커버해야하는 거리가 됩니다.

예를 들어 k=2 인 경우 두 개의 구역으로 나눠질 때 각 집중국이 커버하는 값이 최소가 될 수 있도록 해야하는 것이죠.

따라서 인접한 두 지역 간의 거리가 가장 먼 지역부터 구분을 해주면 되는 것입니다.

 

이해가 잘 안되신다면 좋은 시각 자료를 포함한 다른 게시물 링크를 참고하시면 좋겠습니다.