[백준 2212 / Python] 센서

🧑🏻‍💻 문제링크

문제풀이

N개의 센서가 1, 6, 9, 3, 6, 7로 주어졌을 때 각 집중국의 수신 가능영역 거리의 합의 최솟값을 구하는 탐욕 알고리즘 문제이다. 센서를 오름차순으로 정렬을 했을 때 다음과 같다.

1, 3, 6, 6, 7, 9

이 센서들을 두 개의 영역으로 나타낼 수 있는데 이것이 핵심이다. 각 센서의 거리의 차이가 가장 큰 곳을 기준을 삼아서 두 개의 영역으로 나타내면 다음과 같다.

(1, 3) / (6, 6, 7, 9)

센서 사이의 거리를 계산 후 가장 거리가 먼 순서대로 K-1개의 연결을 제거하면 된다. 무슨 소리인지 잘 이해가 안 되면 코드를 보면 더 이해가 된다.

코드

import sys

N = int(input())    # 센서의 개수
K = int(input())    # 집중국의 개수

temp = []

if K >= N:
    print(0)
    sys.exit()

arr = list(map(int, input().split()))   # N개의 센서 좌표
arr.sort()  # 오름차순으로 정렬

# 각 센서 사이의 거리를 계산
for i in range(1, N):
    temp.append(arr[i] - arr[i-1])

# 가장 거리가 먼 순서대로 K-1 개의 연결 고리를 제거
temp.sort(reverse=True)

for i in range(K-1):
    temp[i] = 0

print(sum(temp))

결과