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

백준 2212번 : 센서 (문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 그리디
• 난이도 : 하

소스코드

import sys

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
pos = sorted(list(map(int, sys.stdin.readline().split())))

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

dist = []
for i in range(1, n):
    dist.append(pos[i] - pos[i-1])

dist.sort(reverse=True)
for _ in range(k-1):
    dist.pop(0)

print(sum(dist))

설명

• 결론적으로 정렬만 수행하면 되므로 시간복잡도 O(NlogN)에 해결 가능
• 결론적으로 문제가 요구하는 것은 n개의 센서들을 k개의 구간으로 나누는 것과 동일하다.

0. 센서 위치를 입력받아 오름차순 정렬한다.
1. 집중국수 k가 센서수 n과 같거나 크다면, 집중국을 센서 위치에 설치하면 되므로 답은 0이 된다.
2. 1이 아니라면, 인접한 센서 사이의 거리를 전부 구해 dist 리스트에 저장한 후 내림 차순 정렬한다.
3. 센서들을 k개의 구간으로 나눠야 하므로, k-1번만큼 반복을 돌며 값이 가장 큰 원소부터 차례로 제거한다.
4. 남은 원소들의 합을 구하여 출력한다.